建站
咨詢
售后
建站咨詢
新聞中心
Part 7 B-Tree簡介
B-tree是SQLite用來表示表和索引的數(shù)據(jù)結(jié)構(gòu)，所以B-tree是非常中心的想法。這個主題主要是介紹B-tree數(shù)據(jù)結(jié)構(gòu)，所以不會有任何的代碼。
成都創(chuàng)新互聯(lián)專注于企業(yè)營銷型網(wǎng)站建設(shè)、網(wǎng)站重做改版、冠縣網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5場景定制、商城網(wǎng)站制作、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為冠縣等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。
為什么說對于數(shù)據(jù)庫來說，樹是非常好的數(shù)據(jù)結(jié)構(gòu)呢？
- 查找特定的value很快（對數(shù)時間花銷，loga N）
- 插入一行或者對查詢到的數(shù)據(jù)刪除很快（再平衡使用常量時間）
- 遍歷一個范圍內(nèi)的value很快（不像hash map）
- B-tree不同于二叉樹（“B”可能代表發(fā)明人的名字，但也可以代表“Balanced”）。這里是一個B-tree例子：
B-Tree 例子(https://en.wikipedia.org/wiki/File:B-tree.svg)
不像二叉樹每個節(jié)點(diǎn)只能有兩個子節(jié)點(diǎn)，B-tree的每個節(jié)點(diǎn)可以有兩個以上的子節(jié)點(diǎn)。每個節(jié)點(diǎn)最多可以有 m 個子節(jié)點(diǎn)，其中 m 叫做樹的“order”（或者叫“階”）。為了保持樹的盡量平衡，我們還要求節(jié)點(diǎn)必須至少有 m / 2 個子節(jié)點(diǎn)（四舍五入）。
但還有一些例外：
- 葉子節(jié)點(diǎn)沒有子節(jié)點(diǎn)
- 根節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)可以少于m，但至少要有兩個
- 如果根節(jié)點(diǎn)也是葉子節(jié)點(diǎn)（樹只有一個節(jié)點(diǎn)），那它有0個子節(jié)點(diǎn)
上面的描述的是一個B-tree，SQLite用它來存儲索引。為了存儲表數(shù)據(jù)，SQLites使用一種B-tree的變體，稱為B+tree。
|
B-tree |
B+ tree | |
|
發(fā)音 |
“Bee Tree” |
“Bee Plus Tree” |
|
用來存儲 |
索引 |
表 |
|
內(nèi)部節(jié)點(diǎn)是否存儲key |
是 |
是 |
|
內(nèi)部節(jié)點(diǎn)是否存儲value |
是 |
否 |
|
每個節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù) |
少 |
多 |
|
內(nèi)部節(jié)點(diǎn) vs 葉子節(jié)點(diǎn) |
相同結(jié)構(gòu) |
不同結(jié)構(gòu) |
在我們開始實(shí)現(xiàn)索引之前，我將只討論B+tree，但這里將其稱為 B-tree 或者 btree。
有子節(jié)點(diǎn)（children）的節(jié)點(diǎn)被稱為“內(nèi)部”節(jié)點(diǎn)（internal node），內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)在結(jié)構(gòu)上不同：
|
m階tree |
內(nèi)部節(jié)點(diǎn) |
葉子節(jié)點(diǎn) |
|
存儲 |
key和指向子節(jié)點(diǎn)的指針 |
key和value |
|
key的數(shù)目 |
最多m-1個 |
越多越好 |
|
指針的數(shù)目 |
keys + 1 |
無 |
|
value的數(shù)目 |
無 |
與key的數(shù)目相同 |
|
Key的用途 |
用來路由 |
與value成對存儲 |
|
存儲value? |
否 |
是 |
這里通過一個例子來看一下，當(dāng)插入一個元素時，B-tree是怎樣發(fā)生結(jié)構(gòu)變化的。為了讓事情看起來更容易理解，這棵B-tree的階（order）設(shè)置為3(m=3)，也就是說：
- 每個內(nèi)部節(jié)點(diǎn)最多有三個子節(jié)點(diǎn)(m)
- 每個內(nèi)部節(jié)點(diǎn)最多有兩個key
- 每個內(nèi)部節(jié)點(diǎn)至少兩個子節(jié)點(diǎn)（m-1）
- 每個內(nèi)部節(jié)點(diǎn)至少一個key
一棵空樹只有一個節(jié)點(diǎn)：根節(jié)點(diǎn)。根節(jié)點(diǎn)最開始也作為葉子節(jié)點(diǎn)，有0個鍵值對（key/value）：
空的btree
如果我們插入兩個鍵值對（超過兩個鍵值對，節(jié)點(diǎn)需要分裂，參考上面規(guī)則），他們會按順序排序存放在葉子節(jié)點(diǎn)中。
一個節(jié)點(diǎn)的btree
我們假設(shè)了節(jié)點(diǎn)的容量是兩個鍵值對兒。當(dāng)我們插入另外一個的時候，就不得不分裂葉子節(jié)點(diǎn)了，分裂后的兩個節(jié)點(diǎn)每個存放之前一半的鍵值對。分裂后的兩個節(jié)點(diǎn)都變成了內(nèi)部節(jié)點(diǎn)，同時也變成了一個新的節(jié)點(diǎn)的子節(jié)點(diǎn)，這個新的節(jié)點(diǎn)變成了根節(jié)點(diǎn)。
兩層的btree
圖中的內(nèi)部節(jié)點(diǎn)（也是根節(jié)點(diǎn)）有一個key和兩個指針指向子節(jié)點(diǎn)（就是那兩條線）。如果我們想查找一個key，key小于或等于5，我們查看左子樹。如果查找的key大于5，就查看右子樹?，F(xiàn)在，準(zhǔn)備插入一個新的key "2"。首先，我們查找它將位于哪個葉節(jié)點(diǎn)（如果它在樹中存在的話），這樣就到達(dá)了左側(cè)葉子節(jié)點(diǎn)。這個節(jié)點(diǎn)是滿的，所以把這個葉子節(jié)點(diǎn)進(jìn)行分裂（split），并在父節(jié)點(diǎn)創(chuàng)建新的條目。
四節(jié)點(diǎn)的btree
現(xiàn)在繼續(xù)增加key，18 和 21 。現(xiàn)在又到了不得不分裂的情況，但是在父節(jié)點(diǎn)中已經(jīng)沒有空間來增加新的鍵值對兒了。
內(nèi)部節(jié)點(diǎn)沒有空間
解決方法就是分裂根節(jié)點(diǎn)為兩個內(nèi)部節(jié)點(diǎn)，然后創(chuàng)建一個新的根節(jié)點(diǎn)作為兩個內(nèi)部節(jié)點(diǎn)的父節(jié)點(diǎn)。
三層的btree
樹只是在我們分裂根節(jié)點(diǎn)的時候才會增加深度。每個葉子節(jié)點(diǎn)都有相同的深度和接近相同的數(shù)量的鍵值對兒，所以樹能夠保持平衡和快速的進(jìn)行查找。
我暫時先不討論從樹中刪除鍵的操作，推遲到實(shí)現(xiàn)插入操作以后。
當(dāng)我們實(shí)現(xiàn)這個數(shù)據(jù)結(jié)構(gòu)時，每個節(jié)點(diǎn)都對應(yīng)一個page。根節(jié)點(diǎn)將在page0中存在。節(jié)點(diǎn)中的子節(jié)點(diǎn)指針將簡單的使用包含子節(jié)點(diǎn)的page number。
本文題目：手寫一個簡單的Database7
URL鏈接：http://m.5511xx.com/article/dhsjsoc.html
