樹簡介
什么是B樹
B樹(Balanced Tree)是一種優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，用一種通俗的話來說：B樹是一種一個節(jié)點可擁有多于兩個子節(jié)點的樹
B樹有兩種衡量標準：階，度。
t度 的B樹就是 2t階 的B樹(這也是B樹的分裂機制決定的)
因為t度的B樹節(jié)點最多有2t個孩子，2t-1個關(guān)鍵字；m階的B樹最多有m個孩子，
其實通過度定義的B樹和通過階數(shù)定義的B樹，區(qū)別就是一個是用的這個B樹節(jié)點的最小度數(shù)一個是用的這個樹節(jié)點的最大度數(shù)。
這里我們統(tǒng)一使用階來描述樹。
一個t階B樹有以下約束：【注意，所有的除法都向上取整】
- 根節(jié)點除外，每個節(jié)點最少有t/2個孩子，最多有t個孩子【也就是說一個節(jié)點最少有t/2-1個值，最多有t-1個值，根節(jié)點除外】
- 根節(jié)點至少有兩個孩子
- 同一節(jié)點x[i],x[i+1]之間的指針指向的子樹的值必須在x[i],x[i+1]之間
B樹的實例
比較有名的B樹有2-3樹，2-3-4樹。
- 其中2-3樹是度數(shù)為1的樹，即最多有三個子樹，也就是每個節(jié)點可以放1，2個值
- 2-3-4樹是度數(shù)為2的樹，最多有四個子樹，每個節(jié)點可以放1，2，3個值
B樹，B-樹的聯(lián)系和區(qū)別
B樹和B-樹是一個東西，會出現(xiàn)這兩種說法只是翻譯時出的意外
B樹的英文名稱是B-Tree。有的人在翻譯時把橫線翻譯成連接符，所以就翻譯成了B樹。有的人認為是減號，就翻譯成了B-樹，正好還有B+，B*，所以即便翻譯成B-也還湊合著說的過去，所以想叫什么就看自己嘍。
B樹，B+樹的區(qū)別和聯(lián)系
B+樹是對B樹的一種變形樹，它與B樹的差異在于：
- 非葉結(jié)點僅具有索引作用，跟記錄有關(guān)的信息均存放在葉結(jié)點中。
- 樹的所有葉結(jié)點構(gòu)成一個有序鏈表，可以按照關(guān)鍵碼排序的次序遍歷全部記錄。
B和B+樹的區(qū)別在于，B+樹的非葉子結(jié)點只包含導航信息，不包含實際的值，所有的葉子結(jié)點和相連的節(jié)點使用鏈表相連，便于區(qū)間查找和遍歷。
B+ 樹的優(yōu)點是：
- 由于B+樹在內(nèi)部節(jié)點上不包含數(shù)據(jù)信息，因此在內(nèi)存頁中能夠存放更多的key。 數(shù)據(jù)存放的更加緊密，具有更好的空間局部性。因此訪問葉子節(jié)點上關(guān)聯(lián)的數(shù)據(jù)也具有更好的緩存命中率。
- B+樹的葉子結(jié)點都是相鏈的，因此對整棵樹的便利只需要一次線性遍歷葉子結(jié)點即可。而且由于數(shù)據(jù)順序排列并且相連，所以便于區(qū)間查找和搜索。而B樹則需要進行每一層的遞歸遍歷。相鄰的元素可能在內(nèi)存中不相鄰，所以緩存命中性沒有B+樹好。
但是B樹也有優(yōu)點，其優(yōu)點在于，由于B樹的每一個節(jié)點都包含key和value，因此經(jīng)常訪問的元素可能離根節(jié)點更近，因此訪問也更迅速。
B+樹和B*樹的卻別和聯(lián)系
B*樹是B+樹的變體，在B+樹的基礎(chǔ)上，B*樹中非根和非葉子結(jié)點再增加指向兄弟的指針；B*樹定義了階為M的樹非葉子結(jié)點關(guān)鍵字個數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）
平衡樹實現(xiàn)的思考
平衡樹的出現(xiàn)是因為。搜索樹的分布一般情況下很不平衡，導致搜索最壞情況下的搜索樹深度可能達到O(n)。而二叉搜索樹的結(jié)構(gòu)完全由節(jié)點插入的順序決定【他是對輸入敏感的】，樹不具有分配節(jié)點去向的能力，所以也無法根據(jù)當前的情況動態(tài)的改變樹的高度，就容易出現(xiàn)極端的情況。
所以我們需要設(shè)計一種結(jié)構(gòu)，能使根節(jié)點擁有對新來的子節(jié)點的動態(tài)分配權(quán)，增加根節(jié)點分配權(quán)的方法就是讓他可以比，讓根節(jié)點有可以權(quán)衡樹平衡程度的信息
- AVL樹的操作思路是先讓節(jié)點插進去，然后判斷，不合適就旋轉(zhuǎn)，把自己轉(zhuǎn)過去，增加兄弟節(jié)點的樹深
- 笛卡爾樹是根據(jù)額外的一個
value通過堆的思想來決定節(jié)點的去向- Treap和笛卡爾樹相似，不過它是一個單純的BBST，所以它的
value隨機生成，用來平衡樹的深度
B樹不是二叉搜索樹，但是你也可以把他看成二叉搜索樹，它用來平衡的方法是緩存：
以2-3樹為例，來了一個值后如果能放在這個節(jié)點，這個節(jié)點就先存著，等這個節(jié)點放不下了，然后再統(tǒng)一決定節(jié)點的去向。
樹操作算法概述
B樹
例子：2-3樹定義
2-3樹是每個非葉子節(jié)點最多有三個子節(jié)點。
- 你可以把它理解成在二叉搜索樹的基礎(chǔ)上增加了一種新的節(jié)點——里面有兩個鍵值，有三個子樹。
- 你也可以用一種更加通俗的名字叫它——3階B樹
例子：2-3-4 樹定義
2-3-4樹就是4階B樹。
樹的操作方法
我們這里主要介紹B樹的插入操作和刪除操作。
搜索
之前我們寫二叉樹是小于就去左邊找，大于就去右邊找。這里在和本節(jié)點中的值比較時就從左往右順序比較即可，找到比inputKey大的key[i]后，順著key[i]的左子樹繼續(xù)向下查詢。
插入
B樹的插入有以下約束：
- 只有葉子節(jié)點可以插入值
- 節(jié)點溢出后進行分裂時，新構(gòu)建的父節(jié)點一定要插入到原來的父節(jié)點的位置
其實這兩個約束也就是我們插入B樹的思路：
- 通過搜索找到合適插入的葉子節(jié)點【插入一定是在葉子節(jié)點中】
- 插入
- 判斷是否溢出，溢出則分裂，將中值移動至父節(jié)點
- 判斷父節(jié)點是否溢出。。。。。。。
- 判斷父節(jié)點的父節(jié)點。。。。。
- 。
- 。
- 一直到根節(jié)點
引用程序員修煉之路的博客的一句話就是：
插入一個元素時，首先在B樹中是否存在，如果不存在，即在葉子結(jié)點處結(jié)束，然后在葉子結(jié)點中插入該新的元素，注意：如果葉子結(jié)點空間足夠，這里需要向右移動該葉子結(jié)點中大于新插入關(guān)鍵字的元素，如果空間滿了以致沒有足夠的空間去添加新的元素，則將該結(jié)點進行“分裂”，將一半數(shù)量的關(guān)鍵字元素分裂到新的其相鄰右結(jié)點中，中間關(guān)鍵字元素上移到父結(jié)點中（當然，如果父結(jié)點空間滿了，也同樣需要“分裂”操作），而且當結(jié)點中關(guān)鍵元素向右移動了，相關(guān)的指針也需要向右移。如果在根結(jié)點插入新元素，空間滿了，則進行分裂操作，這樣原來的根結(jié)點中的中間關(guān)鍵字元素向上移動到新的根結(jié)點中，因此導致樹的高度增加一層。
刪除
講道理，刪除還真的有點復雜，這個涉及到從兄弟節(jié)點、父節(jié)點的借值。思路如下：
- 通過搜索找到要刪除的值所在的節(jié)點
- 刪除此值，然后使用子樹的值來替換：
- 如果這個值的左子樹可以借值的話【去掉一個值還滿足B樹的要求】，就用左子樹的最右節(jié)點來代替
- 如果左子樹不行，但是右子樹可以的話，就用右子樹的最左節(jié)點來代替
- 子樹的值不能滿足替換，如果它的左右兄弟節(jié)點可以，就通過【兄弟節(jié)點——相同的父節(jié)點——本節(jié)點】的方式進行借值
- 如果兄弟節(jié)點也不行，就和相近的兄弟節(jié)點合并成為一個新的節(jié)點
關(guān)鍵代碼
直接放項目的地址了，我是用的java寫的增刪操作，沒有用C。還有就是沒有專門為這個建git，源碼在com.gateway.learn.tree下面。github地址：https://github.com/LiPengcheng1995/gateway-parent.git
插入
這里，插入操作的關(guān)鍵算法如下：
/**
* @Author: lipengcheng20
* @Date: 2018/9/28 14:23
* @Description: 對外暴露，用于在此節(jié)點或此節(jié)點的子節(jié)點中插入key
**/
public BTreeNode findAPlaceAndInsert(int key) {
if (this.getData().size() == 0) {
this.initNodeWithAKey(key);
return this;
}
if (this.getSubTreeNumber() == 0) {
// 是葉子節(jié)點，就在這里插了
// 此節(jié)點定不為空
this.insertKey(key);
return this.checkOverFlowAndReturn();
} else {
for (int i = 0; i < this.getKeyNumber(); i++) {
if (this.getKeyByIndex(i) > key) {
//插入到這個的左子樹中
if (Objects.isNull(this.getSubTreeOnLeftOf(i))) {
//子樹對應(yīng)的為空，直接插進去
BTreeNode temp = new BTreeNode(this.getMAX_SUBTREE_NUMBER());
temp.initNodeWithAKey(key);
this.setSubTreeOnLeftOf(i, temp);
return this;
} else {
//對應(yīng)的子樹不為空，直接在子樹中插，然后根據(jù)實際情況看是不是要分裂
BTreeNode temp = this.getSubTreeOnLeftOf(i).findAPlaceAndInsert(key);
if (temp.getData().size() == 3) {
//子節(jié)點做了分離
this.insertKeyByKeyIndex(i, temp.getKeyByIndex(0));
this.setSubTreeOnLeftOf(i, temp.getSubTreeOnLeftOf(0));
this.setSubTreeOnRightOf(i, temp.getSubTreeOnRightOf(0));
}
return checkOverFlowAndReturn();
}
}
}
//插入到最右邊的子樹
if (Objects.isNull(this.getSubTreeOnRightOf(this.getKeyNumber() - 1))) {
//最右邊子樹對應(yīng)的為空，直接插進去
BTreeNode temp = new BTreeNode(this.getMAX_SUBTREE_NUMBER());
temp.initNodeWithAKey(key);
this.setSubTreeOnRightOf(this.getKeyNumber() - 1, temp);
return this;
} else {
//最右邊對應(yīng)的子樹不為空，直接在子樹中插，然后根據(jù)實際情況看是不是要分裂
BTreeNode temp = this.getSubTreeOnRightOf(this.getKeyNumber() - 1).findAPlaceAndInsert(key);
if (temp.getData().size() == 3) {
//子節(jié)點做了分離
this.insertKeyToTheEnd(temp.getKeyByIndex(0));
this.setSubTreeOnLeftOf(this.getKeyNumber() - 1, temp.getSubTreeOnLeftOf(0));
this.setSubTreeOnRightOf(this.getKeyNumber() - 1, temp.getSubTreeOnRightOf(0));
}
return checkOverFlowAndReturn();
}
}
}
刪除
只寫了偽代碼，感覺有點復雜，就先不寫了
B+樹實現(xiàn)
太難太難
源碼
直接放項目的地址了，我是用的java寫的增刪操作，沒有用C。還有就是沒有專門為這個建git，源碼在com.gateway.common.web.learnTree下面。github地址：https://github.com/LiPengcheng1995/try.git
樹應(yīng)用場景
主要是數(shù)據(jù)庫的搜索和文件系統(tǒng)的搜索。通過多叉樹，這樣可以一次讀取多個節(jié)點，減少換頁。B+樹尤其如此，B+樹非葉子節(jié)點只存儲了“主鍵”。
參考文獻
https://www.cnblogs.com/vincently/p/4526560.html
https://www.cnblogs.com/hdk1993/p/5840599.html
應(yīng)用：http://blog.codinglabs.org/articles/theory-of-mysql-index.html
規(guī)律：
https://blog.csdn.net/pleasecallmewhy/article/details/8451889
https://blog.csdn.net/guoziqing506/article/details/64122287
