https://www.iteye.com/blog/zhuyuehua-1872202
1.索引結構 1.1 B+樹索引結構 從物理上說，索引通常可以分為：磁區和非磁區索引、常規B樹索引、位圖（bitmap）索引、翻轉 （reverse）索引等，其中，B樹索引屬于最常見的索引
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,并調整鍵值，如下圖
2.3 B+樹索引對于更新的管理
而對于值被更新對于索引條目的影響，則可以認為是洗掉和插入的組合，也就是將被更新的舊值對應的索引
條目設定為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欄位來判斷是否有必要重建索引，
clustering_factor是通過oracle的索引得到表資料塊的一個因子，實際上表示index列的排列順序和表中 index這個列的排列順序的關系，索引的重建并不能減少clustering_factor，因為重建index不能改變表中數 據存放的順序，同樣，洗掉后再創建index也不能降低clustering_factor，降低clustering_factor的關鍵在 于重建表里的資料，只有將表里的資料按照索引列排序以后，才能切實有效的降低clustering_factor，但是 如果某個表存在多個索引的時候，需要仔細決定應該選擇哪一個索引列來重建表（因為這樣的索引一個表只 有一個）， 需要注意的是，clustering_factor主要影響index range scan，比如當一個表有1000條資料，200個資料塊 時，當通過索引去讀取這個表時，需要讀取1000個資料塊，你也許覺得奇怪這個表一共才200個資料塊，怎 么會需要讀1000個塊呢？ 這是因為由于資料的存放順序是按object_name來存放的，通過index通過 object_id的順序來讀取表必然導致oracle多次重復讀取一個塊， 當然，在oracle 920 開始，對于cluster_factor 比較接近表塊數量的根據索引的大范圍查詢做了特別的處理， 不再是讀一個索引記錄去搜索一個表記錄了，而是成批處理(通過索引塊一批rowid一次去表塊中獲得一批記 錄)，這樣就大大節約了讀的成本， 關于第四點，建議是不要定期重建索引，可以是定期檢查索引，只在需要時重建索引， 3.3 重建索引對性能的影響 最后我們來看一下重建索引對于性能的提高到底會有什么作用，假設我們有一個表，該表具有1百萬條記錄， 占用了100000個資料塊，而在該表上存在一個索引，在重建之前的pct_used為50%，高度為3，分支節點塊數 為40個，再加一個根節點塊，葉子節點數為10000個；重建該索引以后，pct_used為90%，高度為3，分支節點 塊數下降到20個，再加一個根節點塊，而葉子節點數下降到5000個，那么從理論上說： 1）如果通過索引獲取單獨1條記錄來說： 重建之前的成本：1個根＋1個分支＋1個葉子＋1個表塊＝4個邏輯讀 重建之后的成本：1個根＋1個分支＋1個葉子＋1個表塊＝4個邏輯讀 性能提高百分比：0 2）如果通過索引獲取100條記錄（占總記錄數的0.01%）來說，分兩種情況： 最差的clustering_factor（即該值等于表的資料行數）： 重建之前的成本：1個根＋1個分支＋0.0001*10000（1個葉子）＋100個表塊＝103個邏輯讀 重建之后的成本：1個根＋1個分支＋0.0001*5000（1個葉子）＋100個表塊＝102.5個邏輯讀 性能提高百分比：0.5%（也就是減少了0.5個邏輯讀） 最好clustering_factor（即該值等于表的資料塊）： 重建之前的成本：1個根＋1個分支＋0.0001*10000（1個葉子）＋0.0001*100000（10個表塊）＝13個邏輯讀 重建之后的成本：1個根＋1個分支＋0.0001*5000（1個葉子）＋0.0001*100000（10個表塊）＝12.5個邏輯讀 性能提高百分比：3.8%（也就是減少了0.5個邏輯讀） 3）如果通過索引獲取10000條記錄（占總記錄數的1%）來說，分兩種情況： 最差的clustering_factor（即該值等于表的資料行數）： 重建之前的成本：1
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/50664.html
標籤：MySQL
下一篇：查看MySQL資料庫版本