縱觀
樹結(jié)構(gòu)索引的好處：定位記錄的I/O減少，索引樹的高度一般就是3,4層
樹結(jié)構(gòu)中的兩種結(jié)構(gòu)
1. ISAM結(jié)構(gòu)
2. B+樹結(jié)構(gòu)
ISAM結(jié)構(gòu)（索引順序存取方法）
- 索引樹的結(jié)構(gòu)不變，是靜態(tài)的
- 多個項插入到一個葉子頁，超出了一頁，就需要分配另外的頁，加入溢出頁（這是從溢出區(qū)中分配出來的）
搜索的過程：
搜索的數(shù)據(jù)和索引中的值比較，一層層下去，到達葉子（數(shù)據(jù)頁），然后在主葉子頁中搜索，沒有的話就去主葉子頁對應(yīng)的溢出頁中搜索。
缺點：
- 如果大量的插入操作作用于同一葉子，就會產(chǎn)生很長的溢出頁鏈，這些鏈非常影響搜索記錄的時間。
優(yōu)點：
- 只有葉子葉被修改對于并發(fā)訪問也有好處。當(dāng)一頁被訪問時，會被申請者鎖定，保證它不被該頁的其他用戶并發(fā)修改。
- 索引級的頁從不被修改，可以不對索引級頁加鎖（這是優(yōu)于B+的一個重要優(yōu)點）
- 當(dāng)數(shù)據(jù)分布和大小相對穩(wěn)定而使得溢出鏈很少時，ISAM將優(yōu)于B+樹
B+樹（動態(tài)索引結(jié)構(gòu)）
- 平衡樹
- 葉子頁之間用雙向鏈表
- 只有索引級樹和葉子級樹（即和ISAM相比，沒有溢出頁）
- 每個節(jié)點都要保證最少50%的占有率（假設(shè)，每個節(jié)點包含m個項的B+樹，其中d<=m<=2d，d是B+樹的一個參數(shù)，秩。根節(jié)點是唯一的例外1<=m<=2d）
節(jié)點格式
有m個索引項的非葉子頁節(jié)點包含m+1個指向孩子的指針。葉子頁以雙向鏈表的形式連接起來。
（有關(guān)搜索，插入和刪除的操作，B+都不允許重復(fù)）
搜索
在索引樹上縮小范圍后，通過指針訪問葉子頁，然后繼續(xù)通過雙向鏈表進行搜索
插入
注意分裂的問題，因為B+不加入溢出頁，當(dāng)插入的數(shù)據(jù)多于一個頁都可以存放的量的時候，就需要分裂葉子頁，這里分裂葉子頁過程是這樣的
新插入的8使得新加了一頁，因為每一頁都會有索引指針指向，這就意味這我們要新增索引項，即復(fù)制了5的那項。這一項將會插到父節(jié)點中，因為父節(jié)點又滿了，這就以為這父節(jié)點又要分裂。但是這里的分裂和剛剛的分裂優(yōu)點不一樣。新的項（5的那項）‘彈上去’以后，父節(jié)點要分裂，這時候的中間的那項17是被‘拉上去’而不是復(fù)制的。因為我們這時候不需要副本。
這里也有個變種的方法：就是重分布，搜索兄弟節(jié)點檢查是否還有空位插入。這個想法同樣使用于刪除中。
刪除
刪除需要注意到合并的問題。開始時先考慮是否可以重分布，即搜索兄弟節(jié)點看是否可以‘過繼’過來。如果不行的話，我們就要對兩個節(jié)點進行合并（注意：合并就代表有頁要被刪除，這就代表著指針將會減少，父節(jié)點可能要被‘拉下來’）
