B+樹索引

https://www.iteye.com/blog/zhuyuehua-1872202

   B樹索引是一個典型的樹結構，其包含的組件主要是：

      葉子節點（Leaf node）：包含條目直接指向表裡的數據行。

      分支節點（Branch node）：包含的條目指向索引里其他的分支節點或者是葉子節點。

      根節點（Root node）：一個B樹索引只有一個根節點，它實際就是位於樹的最頂端分支節點。

   可以用下圖一來描述B樹索引的結構。其中，B表示分支節點，而L表示葉子節點。

     對於分支節點塊（包括根節點塊）來說，其所包含的索引條目都是按照順序排列的（預設是升序排列，

也可以在創建索引時指定為降序排列）。每個索引條目（也可以叫做每條記錄）都具有兩個欄位。第一個字

段表示當前該分支節點塊下麵所鏈接的索引塊中所包含的最小鍵值；第二個欄位為四個位元組，表示所鏈接的

索引塊的地址，該地址指向下麵一個索引塊。

     在一個分支節點塊中所能容納的記錄行數由數據塊大小以及索引鍵值的長度決定。

     對於葉子節點塊來說，其所包含的索引條目與分支節點一樣，都是按照順序排列的（預設是升序排列，

也可以在創建索引時指定為降序排列）。每個索引條目（也可以叫做每條記錄）也具有兩個欄位。第一個字

段表示索引的鍵值，對於單列索引來說是一個值；而對於多列索引來說則是多個值組合在一起的。第二個字

段表示鍵值所對應的記錄行的ROWID，該ROWID是記錄行在表裡的物理地址。如果索引是創建在非分區表上或

者索引是分區表上的本地索引的話，則該ROWID占用6個位元組；如果索引是創建在分區表上的全局索引的話，

則該ROWID占用10個位元組。

     1.2 估算索引條目

對於每個索引塊來說，預設的PCTFREE為10％，也就是說最多只能使用其中的90％。同時9i後，這90％

中也不可能用盡，只能使用其中的87％左右。也就是說，8KB的數據塊中能夠實際用來存放索引數據的

空間大約為6488（8192×90％×88％）個位元組。

假設我們有一個非分區表，表名為warecountd，其數據行數為130萬行。該表中有一個列，列名為goodid，其

類型為char（8），那麼也就是說該goodid的長度為固定值：8。同時在該列上創建了一個B樹索引。

在葉子節點中，每個索引條目都會在數據塊中占一行空間。每一行用2到3個位元組作為行頭，行頭用來存放標

記以及鎖定類型等信息。同時，在第一個表示索引的鍵值的欄位中，每一個索引列都有1個位元組表示數據長

度，後面則是該列具體的值。那麼對於本例來說，在葉子節點中的一行所包含的數據大致如下圖二所示：

從上圖可以看到，在本例的葉子節點中，一個索引條目占18個位元組。同時我們知道8KB的數據塊中真正可以用

來存放索引條目的空間為6488位元組，那麼在本例中，一個數據塊中大約可以放360（6488/18）個索引條目。

而對於我們表中的130萬條記錄來說，則需要大約3611（1300000/360）個葉子節點塊。

而對於分支節點里的一個條目（一行）來說，由於它只需保存所鏈接的其他索引塊的地址即可，而不需要保

存具體的數據行在哪裡，因此它所占用的空間要比葉子節點要少。分支節點的一行中所存放的所鏈接的最小

鍵值所需空間與上面所描述的葉子節點相同；而存放的索引塊的地址只需要4個位元組，比葉子節點中所存放

的ROWID少了2個位元組，少的這2個位元組也就是ROWID中用來描述在數據塊中的行號所需的空間。因此，本例中

在分支節點中的一行所包含的數據大致如下圖三所示：

從上圖可以看到，在本例的分支節點中，一個索引條目占16個位元組。根據上面葉子節點相同的方式，我們可

以知道一個分支索引塊可以存放大約405（6488/16）個索引條目。而對於我們所需要的3611個葉子節點來

說，則總共需要大約9個分支索引塊。

這樣，我們就知道了我們的這個索引有2層，第一層為1個根節點，第二層為9個分支節點，而葉子節點數

為3611個，所指向的表的行數為1300000行。但是要註意，在oracle的索引中，層級號是倒過來的，也就是說

假設某個索引有N層，則根節點的層級號為N，而根節點下一層的分支節點的層級號為N-1，依此類推。對本例

來說，9個分支節點所在的層級號為1，而根節點所在的層級號為2。

2. B+樹索引的管理機制

    2.1 B+樹索引對於插入的管理

    對於B樹索引的插入情況的描述，可以分為兩種情況：

    一種是在一個已經充滿了數據的表上創建索引時，索引是怎麼管理的；

    另一種則是當一行接著一行向表裡插入或更新或刪除數據時，索引是怎麼管理的。

對於第一種情況來說，比較簡單。當在一個充滿了數據的表上創建索引（create index命令）時，oracle會

先掃描表裡的數據並對其進行排序，然後生成葉子節點。生成所有的葉子節點以後，根據葉子節點的數量生

成若幹層級的分支節點，最後生成根節點。這個過程是很清晰的。

當一開始在一個空的表上創建索引的時候，該索引沒有根節點，只有一個葉子節點。

隨著數據不斷被插入表裡，該葉子節點中的索引條目也不斷增加，當該葉子節點充滿了索引條目而不能再放

下新的索引條目時，該索引就必須擴張，必須再獲取一個可用的葉子節點。這時，索引就包含了兩個葉子節

點，但是兩個葉子節點不可能單獨存在的，這時它們兩必須有一個上級的分支節點，其實這也就是根節點

了。於是，現在，我們的索引應該具有3個索引塊，一個根節點，兩個葉子節點。

葉子節點的拆分過程。這個過程需要分成兩種情況，一種是插入的鍵值不是最大值；另一種是插入的鍵值是最大值。

對於第一種情況來說，當一個非最大鍵值要進入索引，但是發現所應進入的索引塊不足以容納當前鍵值時：

1）從索引可用列表上獲得一個新的索引數據塊。

2）將當前充滿了的索引中的索引條目分成兩部分，一部分是具有較小鍵值的，另一部分是具有較大鍵值的。

Oracle會將具有較大鍵值的部分移入新的索引數據塊，而較小鍵值的部分保持不動。

3）將當前鍵值插入合適的索引塊中，可能是原來空間不足的索引塊，也可能是新的索引塊。

4）更新原來空間不足的索引塊的kdxlenxt信息，使其指向新的索引塊。

5）更新位於原來空間不足的索引塊右邊的索引塊里的kdxleprv，使其指向新的索引塊。

6）向原來空間不足的索引塊的上一級的分支索引塊中添加一個索引條目，該索引條目中保存新的索引塊里的最小鍵值，以及新的索引塊的地址。

從上面有關葉子節點分裂的過程可以看出，其過程是非常複雜的。因此如果發生的是第二種情況，則為了簡

化該分裂過程，oracle省略了上面的第二步，而是直接進入第三步，將新的鍵值插入新的索引塊中。

在上例中，當葉子節點越來越多，導致原來的根節點不足以存放新的索引條目（這些索引條目指向葉子節

點）時，則該根節點必須進行分裂。當根節點進行分裂時：

1）從索引可用列表上獲得兩個新的索引數據塊。

2）將根節點中的索引條目分成兩部分，這兩部分分別放入兩個新的索引塊，從而形成兩個新的分支節點。

3）更新原來的根節點的索引條目，使其分別指向這兩個新的索引塊。

因此，這時的索引層次就變成了2層。同時可以看出，根節點索引塊在物理上始終都是同一個索引塊。而隨著

數據量的不斷增加，導致分支節點又要進行分裂。分支節點的分裂過程與根節點類似（實際上根節點分裂其

實是分支節點分裂的一個特例而已）：

1）從索引可用列表上獲得一個新的索引數據塊。

2）將當前滿了的分支節點里的索引條目分成兩部分，較小鍵值的部分不動，而較大鍵值的部分移入新的索引塊。

3）將新的索引條目插入合適的分支索引塊。

4）在上層分支索引塊中添加一個新的索引條目，使其指向新加的分支索引塊。

當數據量再次不斷增加，導致原來的根節點不足以存放新的索引條目（這些索引條目指向分支節點）時，再

次引起根節點的分裂，其分裂過程與前面所說的由於葉子節點的增加而導致的根節點分裂的過程是一樣的。

同時，根節點分裂以後，索引的層級再次遞增。由此可以看出，根據B樹索引的分裂機制，一個B樹索引始終

都是平衡的。註意，這裡的平衡是指每個葉子節點與根節點的距離都是相同的。同時，從索引的分裂機制可

以看出，當插入的鍵值始終都是增大的時候，索引總是向右擴展；而當插入的鍵值始終都是減小的時候，索

引則總是向左擴展。

圖解B+數的插入：

    例1：

    往下圖的3階B+樹中插入關鍵字9

    首先查找9應插入的葉節點(最左下角的那一個),插入發現沒有破壞B+樹的性質,完畢。插完如下圖所示:

    例2：

    往下圖的3階B+樹插入20

    首先查找20應插入的葉節點(第二個葉子節點),插入，如下圖

    發現第二個葉子節點已經破壞了B+樹的性質,則把之分解成[20 21], [37 44]兩個,並把21往父節點移，如下圖

    發現父節點也破壞了B+樹的性質,則把之再分解成[15 21], [44 59]兩個,並把21往其父節點移，如下圖

    這次沒有破壞B+樹的性質(如果還是不滿足B+樹的性質,可以遞歸上去,直到滿足為至),插入完畢。

     例3：

    往下圖的3階B+樹插入100

首先查找100應插入的葉節點(最後一個節點), 插入，如下圖

修改其所有父輩節點的鍵值為100(只有插入比當前樹的最大數大的數時要做此步),如下圖

然後重覆Eg.2的方法拆分節點,最後得

2.2 B+樹索引對於刪除的管理

1）當刪除表裡的一條記錄時，其對應於索引里的索引條目並不會被物理的刪除，只是做了一個刪除標記。

2）當一個新的索引條目進入一個索引葉子節點的時候，oracle會檢查該葉子節點里是否存在被標記為刪除的

索引條目，如果存在，則會將所有具有刪除標記的索引條目從該葉子節點里物理的刪除。

3）當一個新的索引條目進入索引時，oracle會將當前所有被清空的葉子節點（該葉子節點中所有的索引條目

都被設置為刪除標記）收回，從而再次成為可用索引塊。

儘管被刪除的索引條目所占用的空間大部分情況下都能夠被重用，但仍然存在一些情況可能導致索引空間被

浪費，並造成索引數據塊很多但是索引條目很少的後果，這時該索引可以認為出現碎片。而導致索引出現碎

片的情況主要包括：

1）不合理的、較高的PCTFREE。很明顯，這將導致索引塊的可用空間減少。

2）索引鍵值持續增加（比如採用sequence生成序列號的鍵值），同時對索引鍵值按照順序連續刪除，這時可

能導致索引碎片的發生。因為前面我們知道，某個索引塊中刪除了部分的索引條目，只有當有鍵值進入該索

引塊時才能將空間收回。而持續增加的索引鍵值永遠只會向插入排在前面的索引塊中，因此這種索引里的空

間幾乎不能收回，而只有其所含的索引條目全部刪除時，該索引塊才能被重新利用。

3）經常被刪除或更新的鍵值，以後幾乎不再會被插入時，這種情況與上面的情況類似。

對於如何判斷索引是否出現碎片，方法非常簡單：直接運行ANALYZE INDEX … VALIDATE STRUCTURE命令，然

後檢查index_stats視圖的pct_used欄位，如果該欄位過低（低於50％），則說明存在碎片。

圖解B+數的刪除：

    例1：

    刪除下圖3階B+樹的關鍵字91

首先找到91所在葉節點(最後一個節點),刪除之，如下圖

沒有破壞B+樹的性質,刪除完畢

    例2：

    刪除下圖3階B+樹的關鍵字97

    首先找到97所在葉節點(最後一個節點),刪除之，然後修改該節點的父輩的鍵字為91(只有刪除樹中最大數時要做此步)，如下圖

    例3：

    刪除下圖3階B+樹的關鍵字51

首先找到51所在節點(第三個節點),刪除之，如下圖

破壞了B+樹的性質,從該節點的兄弟節點(左邊或右邊)借節點44，並修改相應鍵值,判斷沒有破壞B+樹,完畢，如下圖

    例4：

    刪除下圖3階B+樹的關鍵字59

首先找到59所在葉節點(第三個節點),刪除之，如下圖

破壞B+樹性質,嘗試借節點,無效(因為左兄弟節點被借也會破壞B+樹性質),合併第二第三葉節點並調整鍵值，如下圖

完畢。

     例5：

    刪除下圖3階B+樹的關鍵字63

首先找到63所在葉節點(第四個節點),刪除之，如下圖

合併第四五葉節點並調整鍵值，如下圖

發現第二層的第二個節點不滿足B+樹性質,從第二層的第一個節點借59,並調整鍵值，如下圖

而對於值被更新對於索引條目的影響，則可以認為是刪除和插入的組合。也就是將被更新的舊值對應的索引

條目設置為D（刪除）標記，同時將更新後的值按照順序插入合適的索引塊中。這裡就不重覆討論了。

3. 重建索引

3.1 如何重建索引

    ALTER INDEX … REBUILD

3.2 重建索引的好處

當我們重建索引以後，在物理上所能獲得的好處就是能夠減少索引所占的空間大小（特別是能夠減少葉子節

點的數量）。而索引大小減小以後，又能帶來以下若幹好處：

1）CBO對於索引的使用可能會產生一個較小的成本值，從而在執行計劃中選擇使用索引。

2）使用索引掃描的查詢掃描的物理索引塊會減少，從而提高效率。

3）由於需要緩存的索引塊減少了，從而讓出了記憶體以供其他組件使用。

儘管重建索引具有一定的好處，但是盲目的認為重建索引能夠解決很多問題也是不正確的。比如我見過一個

生產系統，每隔一個月就要重建所有的索引（而且我相信，很多生產系統可能都會這麼做），其中包括一些

100GB的大表。為了完成重建所有的索引，往往需要把這些工作分散到多個晚上進行。事實上，這是一個

7×24的系統，僅重建索引一項任務就消耗了非常多的系統資源。但是每隔一段時間就重建索引有意義嗎？這

里就有一些關於重建索引的很流行的說法，主要包括：

1）如果索引的層級超過X（X通常是3）級以後需要通過重建索引來降低其級別。

2）如果經常刪除索引鍵值，則需要定時重建索引來收回這些被刪除的空間。

3）如果索引的clustering_factor很高，則需要重建索引來降低該值。

4）定期重建索引能夠提高性能。

對於第一點來說，我們在前面已經知道，B樹索引是一棵在高度上平衡的樹，所以重建索引基本不可能降低其

級別，除非是極特殊的情況導致該索引有非常大量的碎片，導致B樹索引“虛高”，那麼這實際又來到第二點

上（因為碎片通常都是由於刪除引起的）。實際上，對於第一和第二點，我們應該通過運行ALTER INDEX …

REBUILD命令以後檢查indest_stats.pct_used欄位來判斷是否有必要重建索引。