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