文件储存树的理解（ISAM 和 B+Tree）
兩種文件儲(chǔ)存樹的理解（ISAM 和 B+Tree）
1. 文件簡要概括
如何儲(chǔ)存文件？如何快速的查找到所需文件？我們需要引入索引(index)這個(gè)概念。想象在圖書館中的分類，每一本書都有一個(gè)所屬區(qū)域、類別、獨(dú)一無二的id。根據(jù)這些索引信息，我們就能在書海中快速查找到特定的書籍。那對計(jì)算機(jī)文件而言，我們需要有索引文件（index file）、儲(chǔ)存的信息(record)。
1.1 Index file是什么
Index file用來儲(chǔ)存多個(gè)index entries。
Index entries, 需要儲(chǔ)存兩個(gè)信息：查找鍵（search key）、指針（pointer）。
查找鍵是由一個(gè)或多個(gè)屬性組成，用于對數(shù)據(jù)進(jìn)行查找的索引。例如：學(xué)生的id、用戶年齡等等。
指針存放的是對應(yīng)index entries或者record的地址。
2. Indexed Sequential Access Method（ISAM）
2.1 ISAM的結(jié)構(gòu)
要想結(jié)構(gòu)化儲(chǔ)存大量文件，我們需要Index file 和 Data File。為每一個(gè)record分配一個(gè)Index Entry，并對search key（K0， K1， K2等）進(jìn)行排序，這樣我們也可以對Index File進(jìn)行二分查找（Binary Search）。
具體結(jié)構(gòu)圖如下：
2.2 ISAM的樹狀結(jié)構(gòu)
但是上述儲(chǔ)存結(jié)構(gòu)還是不夠高效， 因?yàn)镮ndex File依舊可能會(huì)很大。所以我們引入樹狀結(jié)構(gòu)。
根據(jù)Search Key進(jìn)行分類。從上至下為根節(jié)點(diǎn)、子（樹）節(jié)點(diǎn)、葉節(jié)點(diǎn)。
結(jié)構(gòu)圖如下：
2.2.1 查找操作
等式查找
舉個(gè)栗子，假設(shè)我們想在下圖中查找Search Key為27所保存的record， 每一個(gè)節(jié)點(diǎn)只能保存兩個(gè)Search Key。首先我們在根節(jié)點(diǎn)（Root）判斷27<40， 故選擇左節(jié)點(diǎn)。接著在第二層進(jìn)行判斷， 22 < 27 < 33，選擇中間節(jié)點(diǎn)指向葉節(jié)點(diǎn)，在其中查找到27。
具體圖示如下：（每一個(gè)框中的數(shù)字均為Search Key，*為葉節(jié)點(diǎn)）
范圍查找
繼續(xù)舉個(gè)例子，假設(shè)我們要查找40<= x <63，首先，從根節(jié)點(diǎn)判斷大于40，選擇右邊節(jié)點(diǎn)，繼續(xù)判斷40 < 51，選擇51左邊的pointer指向的文件，從對應(yīng)的葉子節(jié)點(diǎn)頁中查找出相應(yīng)大于40的Search Key（40*）。重復(fù)上述操作，直到查找到小于63*的數(shù)據(jù)。
2.2.2 插入操作
假設(shè)每一個(gè)Page只能保存兩個(gè)Search Key。當(dāng)Page中沒有空余位置時(shí)，ISAM會(huì)鏈接一個(gè)額外的page來存儲(chǔ)這個(gè)search key，即overflow page。如下圖所示，假設(shè)插入23*、48*、41*、42*。
假設(shè)這棵樹有很多的Overflow Page，這樣會(huì)導(dǎo)致產(chǎn)生很長的鏈表，并且存儲(chǔ)的Search Key是隨機(jī)的，查找很不方便，效率降低。
2.2.3 刪除操作
ISAM的刪除操作很簡單，只刪除葉節(jié)點(diǎn)中的Search Key如果刪除相對應(yīng)的文件后，此Page中的Search Key為空，則刪除此Page。
例如：刪除上圖中的51*，只會(huì)刪除在Primary Leaf Pages中的51*，還會(huì)保留Index Page中的51.
3. B+ Tree
2.1 什么是B+ Tree
B+ Tree是一種具有動(dòng)態(tài)深度的樹狀結(jié)構(gòu)。由于前文中，ISAM結(jié)構(gòu)可能會(huì)產(chǎn)生大量的Overflow Pages，對文件的查找操作造成極大的影響，并且只能對葉子節(jié)點(diǎn)進(jìn)行修改，所以引入了B+ Tree這一結(jié)構(gòu)來對其進(jìn)行改進(jìn)。
一般為了提高搜索效率，樹的高度要盡可能地低，一般為3-4層，而且是高度集成的，即每一個(gè)葉子節(jié)點(diǎn)中盡可能多的存儲(chǔ)值。此外，在葉結(jié)點(diǎn)中，每個(gè)page之間互相連接，這樣便于范圍查找。如下圖所示：
另外，需要規(guī)定B+ Tree中每一個(gè)節(jié)點(diǎn)中的最小占有率，此文一律使用最小為50%。即上圖中每個(gè)節(jié)點(diǎn)儲(chǔ)存數(shù)目不允許小于2.
2.2 樹的操作邏輯
2.2.1 查找數(shù)據(jù)
查找方式同ISAM相同。具體可以查看ISAM的查找數(shù)據(jù)方式。
2.2.2 插入數(shù)據(jù)
2.2.2.1 不允許重新分配
在B+ Tree中插入新的數(shù)據(jù)要滿足一下流程：
如果L中依然有空余位置插入，則將值插入即可。
若無空余位置，則將該葉節(jié)點(diǎn)L分裂成為兩個(gè)節(jié)點(diǎn)新的L和L2，并將L和新數(shù)據(jù)均勻地分配給兩個(gè)新節(jié)點(diǎn)，并將其中的中間值復(fù)制Copy Up到上一層節(jié)點(diǎn)中。再將L和L2鏈接起來。
將樹節(jié)點(diǎn)分裂成為兩個(gè)新的節(jié)點(diǎn)，將數(shù)據(jù)均勻的分配，并將中間值推到Push Up更上一層的節(jié)點(diǎn)。
注意：此處區(qū)別Copy Up and Push Up。樹節(jié)點(diǎn)分裂后要push，葉子節(jié)點(diǎn)分類后用copy。
下圖演示插入8*的過程：
2.2.2.2 允許重新分配
在插入一個(gè)數(shù)據(jù)后，葉節(jié)點(diǎn)出現(xiàn)overflow page，此時(shí)檢查該葉節(jié)點(diǎn)同父節(jié)點(diǎn)下的相鄰節(jié)點(diǎn)是否存在空余空間，若存在，則將該值插入相鄰兄弟節(jié)點(diǎn)，并將上一級(jí)樹節(jié)點(diǎn)重新分配；反之執(zhí)行分裂、插入操作。
下圖給出示例：
2.2.3 刪除數(shù)據(jù)
假設(shè)要插入19和20，示例如下：
插入后結(jié)果如下：
現(xiàn)在，假設(shè)我們接著要繼續(xù)刪除24*，由上圖可知，其同父節(jié)點(diǎn)下的兄弟節(jié)點(diǎn)無法滿足重新分配的條件，所以選擇將兩個(gè)葉子節(jié)點(diǎn)進(jìn)行合并，并修改他們的父節(jié)點(diǎn)、刪除相應(yīng)的指針。示例如下：
合并操作后，他們的樹節(jié)點(diǎn)出現(xiàn)不滿足50%占比的情況，所以同樣對樹節(jié)點(diǎn)和根節(jié)點(diǎn)進(jìn)行同樣的合并操作，得到如下圖所示的結(jié)構(gòu)：
3. 總結(jié)
- ISAM：
- 靜態(tài)樹
- 存在overflow pages，會(huì)降低操作效率
- 只允許修改葉子節(jié)點(diǎn)，不允許修改樹節(jié)點(diǎn)。
- B+ Tree
- 動(dòng)態(tài)樹，樹的高度降低，集成度高。
- 不存在overflow pages，效率比ISAM高
- 能動(dòng)態(tài)地修改根節(jié)點(diǎn)、樹節(jié)點(diǎn)、和葉子節(jié)點(diǎn)。
總結(jié)
以上是生活随笔為你收集整理的文件储存树的理解（ISAM 和 B+Tree）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
