B樹索引

https://www.cnblogs.com/xqzt/p/4456746.html

 B-Tree索引是最常見的索引結構，默認創建的索引就是B-Tree索引，

一、B樹索引的結構

B-樹索引是基于二叉樹結構的，B-樹索引結構有3個基本組成部分：根節點、分支節點和葉子節點，其中根節點位于索引結構的最頂端，而葉子節點位于索引結構的最底端，中間為分子節點，

    葉子節點（Leaf node）：包含條目直接指向表里的資料行，

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

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

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

1.1關于分支節點塊（包括根節點塊）

1、 其所包含的索引條目都是按照順序排列的（預設是升序排列，也可以在創建索引時指定為降序排列），

2、 每個索引條目（也可以叫做每條記錄）都具有兩個欄位，第一個欄位表示當前該分支節點塊下面所鏈接的索引塊中所包含的最小鍵值；第二個欄位為四個位元組，表示所鏈接的索引塊的地址，該地址指向下面一個索引塊，

3、 在一個分支節點塊中所能容納的記錄行數由資料塊大小以及索引鍵值的長度決定，比如從上圖一可以看到，對于根節點塊來說，包含三條記錄，分別為（0 B1）、（500 B2）、（1000 B3），它們指向三個分支節點塊，其中的0、500和1000分別表示這三個分支節點塊所鏈接的鍵值的最小值，而B1、B2和B3則表示所指向的三個分支節點塊的地址，

1.2關于葉子節點

1、 B樹索引的所有葉子塊一定位于同一層上，這是由B樹的資料結構定義的，Oracle 設計的B樹索引結構保證了B 樹索引從根到葉子都有相等的分支節點，保證了B樹索引的平衡，這樣就不會因為基表的資料插入后洗掉操作造成B樹索引變得不平衡，從而影響索引的性能，因此，從根塊到達任何一個葉子塊的遍歷代價都是相同的； 索引高度是指從根塊到達葉子塊時所遍歷的資料塊的個數，通常，大多數的B樹索引的高度都是2到3，也就意味著，即使表中有上百萬條記錄，從索引中定位一個鍵字只需要2或3次I/O,索引越高，性能越差；

2、 葉子節點所包含的索引條目與分支節點一樣，都是按照順序排列的（預設是升序排列，也可以在創建索引時指定為降序排列）

3、 每個索引條目（也可以 叫做每條記錄）也具有兩個欄位，第一個欄位表示索引的鍵值，對于單列索引來說是一個值；而對于多列索引來說則是多個值組合在一起的，第二個欄位表示鍵值所對應的記錄行的ROWID，該ROWID是記錄行在表里的物理地址，ROWID 是唯一的Oracle 指標，指向該行的物理位置，使用ROWID 是Oracle 資料庫中訪問行最快的方法，參照Oracle中的rowid

4、 葉子節點其實是一個雙向鏈表，每個葉子節點包含一個指向下一個和上一個葉子點的指標，這樣在一定范圍內便利索引以搜索需要的記錄，

二、B樹索引的訪問

當oracle行程需要訪問資料檔案里的資料塊時，oracle會有兩種型別的I/O操作方式：
1） 隨機訪問，每次讀取一個資料塊（通過等待事件“db file sequential read”體現出來），
2） 順序訪問，每次讀取多個資料塊（通過等待事件“db file scattered read”體現出來），
第一種方式則是訪問索引里的資料塊，而第二種方式的I/O操作屬于全表掃描，這里順帶有一個問題，為何隨機訪問會對應到db file sequential read等待事件，而順序訪問則會對應到db file scattered read等待事件呢？這似乎反過來了，隨機訪問才應該是分散（scattered）的，而順序訪問才應該是順序（sequential）的，其實，等待事件主要根據實際獲取物理I/O塊的方式來命名的，而不是根據其在I/O子系統的邏輯方式來命名的，下面對于如何獲取索引資料塊的方式中會對此進行說明，
事實上在B樹索引雖然為一個樹狀的立體結構，但其對應到資料檔案里的排列當然還是一個平面的形式，也就是像下面這樣，
/根/分支/分支/葉子/…/葉子/分支/葉子/葉子/…/葉子/分支/葉子/葉子/…/葉子/分支/.....
因此，當oracle需要訪問某個索引塊的時候，勢必會在這個結構上跳躍的移動，
當oracle需要獲得一個索引塊時，首先從根節點開始，根據所要查找的鍵值，從而知道其所在的下一層的分支節點，然后訪問下一層的分支節點，再次同樣根據鍵值訪問再下一層的分支節點，如此這般，最終訪問到最底層的葉子節點，可以看出，其獲得物理I/O塊時，是一個接著一個，按照順序，串行進行的，在獲得最終物理塊的程序中，我們不能同時讀取多個塊，因為我們在沒有獲得當前塊的時候是不知道接下來應該訪問哪個塊的，因此，在索引上訪問資料塊時，會對應到 db file sequential read等待事件，其根源在于我們是按照順序從一個索引塊跳到另一個索引塊，從而找到最終的索引塊的，
那么對于全表掃描來說，則不存在訪問下一個塊之前需要先訪問上一個塊的情況，全表掃描時，oracle知道要訪問所有的資料塊，因此唯一的問題就是盡可能高效的訪問這些資料塊，因此，這時oracle可以采用同步的方式，分幾批，同時獲取多個資料塊，這幾批的資料塊在物理上可能是分散在表里的，因此其對應到db file scattered read等待事件，

三、DML對B樹索引的影響

3.1 INSERT

在每個INSERT操作程序中，關鍵字必須被插入在正確葉節點的位置，如果葉節點已滿，不能容納更多的關鍵字，就必須將葉節點拆分，拆分的方法有兩種：

1)如果新關鍵字值在所有舊葉節點塊的所有關鍵字中是最大的，那么所有的關鍵字將按照99:1的比例進行拆分，使得在新的葉節點塊中只存放有新關鍵字，而其他的所有關鍵字（包括所有洗掉的關鍵字）仍然保存在舊葉節點塊中，
2)如果新關鍵字值不是最大的，那么所有的關鍵字將按照50:50的比例進行拆分，這時每個葉節點塊（舊與新）中將各包含原始葉節點中的一半關鍵字，
這個拆分必須通過一個指向新葉節點的新入口向上傳送到父節點，如果父節點已滿，那么這個父節點也必須進行拆分，并且需要將這種拆分向上傳送到父節點的父節點，這時，如果這個父節點也已滿，將繼續進行這個程序，這樣，某個拆分可能最終被一直傳送到根節點，如果根節點滿了，根結點也將進行分裂，根結點在進行分裂的時候，就是樹的高度增加的時候，根節點進行分裂的方式跟其他的的節點分裂的方式相比較，在物理位置上的處理也是不同的，根節點分裂時，將原來的根結點分裂為分支節點或葉節點，保存到新的塊中，而將新的根節點資訊保存到原來的根結點塊中，這樣做的是為因為避免修改資料字典所帶來的相對較大的開銷，
注意：現在Oracle都是采用了平衡演算法，正常情況下即使索引關鍵字不斷增大，也不會產生不平衡樹，當索引關鍵字不斷增大，導致樹級別單方向增長時，Oracle會自動進行索引翻轉以維持索引的平衡，當然這種操作非常消耗資源
在索引的每一個層次之間，每一個層最左邊的節點的block頭部都有一個指向下層最左邊的塊的指標，這樣有利于fast full scan 的快速定位最左邊的葉子節點，
每個拆分程序都是要花費一定的開銷的，特別是要進行物理硬碟I/O動作，此外，在進行拆分之前，Oracle必須查找到一個空塊，用來保存這個拆分，可以用以下步驟來進行查找空塊的動作：
1) 在索引的自由串列(free-list, 又稱為空閑串列) 中查到一個空閑塊，可以通過CREATE/ALTER INDEX命令為一個索引定義多個空閑串列，索引空閑串列并不能幫助Oracle查找一個可用來存放將要被插入的新關鍵字的塊，這是因為關鍵字值不能隨機地存放在索引中可用的第一個“空閑”葉節點塊中，這個值必須經過適當的排序之后，放置在某個特定的葉節點塊中，只有在塊拆分程序中才需要使用索引的空閑串列，每個空閑串列都包含有一個關于“空”塊的鏈接串列，當為某個索引定義了多個空閑串列時，首先將從分配給行程的空間串列中掃描一個空閑塊，如果沒有找到所需要的空閑塊，將從主空閑串列中進行掃描空閑塊的動作，
2) 如果沒有找到任何空閑塊，Oracle將試圖分配另一個擴展段，如果在表空間中沒有更多的自由空間，Oracle將產生錯誤ORA-01654，
3) 如果通過上述步驟，找到了所需的空閑塊，那么這個索引的高水位標(HWM)將加大，
4) 所找到的空閑塊將用來執行拆分動作，
在創建B*樹索引時，一個需要注意的問題就是要避免在運行時進行拆分，或者，要在索引創建程序中進行拆分（“預拆分”），從而使得在進行拆分時能夠快速命中，以便避免運行時插入動作，當然，這些拆分也不僅僅局限于插入動作，在進行更新的程序中也有可能會發生拆分動作，

3.2 UPDATE

索引更新完全不同于表更新，在表更新中，資料是在資料塊內部改變的（假設資料塊中有足夠的空間來允許進行這種改變）；但在索引更新中，如果有關鍵字發生改變，那么它在樹中的位置也需要發生改變，請記住，一個關鍵字在B*樹中有且只有一個位置，因此，當某個關鍵字發生改變時，關鍵字的舊表項必須被洗掉，并且需要在一個新的葉節點上創建一個新的關鍵字，舊的表項有可能永遠不會被重新使用，這是因為只有在非常特殊的情況下， Oracle才會重用關鍵字表項槽，例如，新插入的關鍵字正好是被洗掉的那個關鍵字（包括資料型別、長度等等），（這里重用的是塊，但完全插入相同的值的時候，也不一定插入在原來的被洗掉的位置，只是插入在原來的塊中，可能是該塊中的一個新位置，也正因為如此，在索引塊中保存的的記錄可能并不是根據關鍵字順序排列的，隨著update等的操作，會發生變化，）那么，這種情況發生的可能性有多大呢？許多應用程式使用一個數列來產生NUMBER關鍵字（特別是主關鍵字），除非它們使用了RECYCLE選項，否則這個數列將不會兩次產生完全相同的數，這樣，索引中被洗掉的空間一直沒有被使用，這就是在大規模洗掉與更新程序中，表大小不斷減小或至少保持不變但索引不斷加大的原因，

3.3 DELETE

當洗掉表里的一條記錄時，其對應于索引里的索引條目并不會被物理的洗掉，只是做了一個洗掉標記，當一個新的索引條目進入一個索引葉子節點的時候，oracle會檢查該葉子節點里是否存在被標記為洗掉的索引條目，如果存在，則會將所有具有洗掉標記的索引條目從該葉子節點里物理的洗掉，
當一個新的索引條目進入索引時，oracle會將當前所有被清空的葉子節點（該葉子節點中所有的索引條目都被設定為洗掉標記）識訓，從而再次成為可用索引塊，
盡管被洗掉的索引條目所占用的空間大部分情況下都能夠被重用，但仍然存在一些情況可能導致索引空間被浪費，并造成索引資料塊很多但是索引條目很少的后果，這時該索引可以認為出現碎片，而導致索引出現碎片的情況主要包括：
1、不合理的、較高的PCTFREE，很明顯，這將導致索引塊的可用空間減少，
2、索引鍵值持續增加（比如采用sequence生成序列號的鍵值），同時對索引鍵值按照順序連續洗掉，這時可能導致索引碎片的發生，因為前面我們知道，某個索引塊中洗掉了部分的索引條目，只有當有鍵值進入該索引塊時才能將空間識訓，而持續增加的索引鍵值永遠只會向插入排在前面的索引塊中，因此這種索引里的空間幾乎不能識訓，而只有其所含的索引條目全部洗掉時，該索引塊才能被重新利用，
3、經常被洗掉或更新的鍵值，以后幾乎不再會被插入時，這種情況與上面的情況類似，

四、總結

通過上面對B樹的分析，可以得出以下的應用準則：
1、避免對那些可能會產生很高的更新動作的列進行索引，
2、避免對那些經常會被洗掉的表中的多個列進行索引，若有可能，只對那些在這樣的表上會進行洗掉的主關鍵字與/或列進行索引，如果對多個列進行索引是不可避免的，那么就應該考慮根據這些列對表進行劃分，然后在每個這樣的劃分上執行TRUNCATE動作（而不是DELETE動作），TRUNCATE在與 DROP STORAGE短語一同使用時，通過重新設定高水位標來模擬洗掉表與索引以及重新創建表與索引的程序，
3、避免為那些唯一度不高的列創建B*樹索引，這樣的低選擇性將會導致樹節點塊的稠密性，從而導致由于索引“平鋪( flat)”而出現的大規模索引掃描，唯一性的程度越高，性能就越好，因為這樣能夠減少范圍掃描，甚至可能用唯一掃描來取代范圍掃描，
4）空值不存盤在單列索引中，對于復合索引的方式，只有當某個列不空時，才需要進行值的存盤，在為DML陳述句創建IS NULL或IS NOT NULL短語時，應該切記這個問題，
5）IS NULL不會導致索引掃描，而一個沒有帶任何限制的IS NOT NULL則可能會導致完全索引掃描，

參考

B+樹索引

Oracle中B-TREE索引的深入理解(原創)

標籤：MySQL

上一篇：mysql引數max_binlog_cache_size設定不當引發的血案

下一篇：B樹和B+樹原理及在索引中的應用