https://www.cnblogs.com/xqzt/p/4456746.html B-Tree索引是最常見的索引結構，預設創建的索引就是B-Tree索引。 一、B樹索引的結構 B-樹索引是基於二叉樹結構的。B-樹索引結構有3個基本組成部分：根節點、分支節點和葉子節點。其中根節點位於索引結構的最 ...
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則可能會導致完全索引掃描。
