Mysql-索引-BTree類型【精簡】

網路上看了很多關於B-TREE的總結，b樹,B-樹,B+樹,B*樹(艾瑪怎麼還4個呢？都快蒙圈了呢)，

有的真的很精彩令人佩服，但是都是篇幅太長啊，一大長段的文字就讓人望而生畏啊。乾脆做一個簡化版的總結，通俗移動點介紹下，說說他們的區別。
一.B樹

#Binary Tree，就是一個二元樹。 (什麼K呀h，n啥的公式這裡不說了，有興趣的可以自己搜搜..)

（1）所有非葉子結點至多擁有兩個兒子（Left和Right）；

（2）所有結點儲存一個關鍵字;

#（3）非葉子結點的左指標指向小於其關鍵字的子樹，右邊指標指向大於其關鍵字的子樹；（簡單說，左邊比自己小，右邊比自己大）

圖片

B樹

############################

#二.B-樹

平衡二元樹（Balance Binary Tree） --AVL樹【這裡的B，其實是balance的意思~】

（1）根節點的左子樹和右子樹的深度最多相差1.(確保了不會出現上圖右邊的極端現象)

（2）根節點的左子樹和右子樹葉都是一棵##平衡二元樹。

（3）所有結點都有儲存#關鍵字;

無論插入的序列是怎麼樣，我們都能透過調整來建構一棵平衡二元樹，保證二元樹中的每個節點的平衡因子都不會大於1，保證了樹的深度達到最淺，從而比較的次數就會更少，時間複雜度就會降低

#圖B-樹

###三.B+樹#############

B+的搜尋與B-樹也基本相同，差異是B+樹只有達到葉子結點才命中（B-樹可以在非葉子結點命中）

（1）所有關鍵字都出現在葉子結點的鍊錶中（稠密索引），且鍊錶中的關鍵字恰好是有序的；（#只有根節點儲存關鍵字最後樹的末梢才有值)

#（2）非葉子結點相當於葉子結點的索引（稀疏索引），葉子結點相當於是儲存（關鍵字）資料的資料層。 （非根節點，儲存的其實是指向根節點的索引#）

（3 ) 因為前兩點，所以不可能在非葉子結點存資料。 (區別B-的第三條)

（4）根節點橫向也有鏈指針(方便快速順藤摸瓜嘛，沒這個指針，就算下一個取的值是挨著的鄰居，也得跑個圈才能拿到)

注意，我們一般用到的索引結果，或通常指的B-TREE結構，大部分就是在說B+結構啦~~

圖B+樹

四.B*樹#是B+

樹的變體，#########

（1）B+樹的非根和非葉子結點再增加指向兄弟的指針；[對比上邊B+的第4條，在非根節點也加入橫向鍊錶]

#圖B * 樹

##B樹：二元樹，

每個結點只儲存一個關鍵字，等於則命中，小於走左結點，大於走右結點；(

但B樹在經過多次插入與刪除後，有可能導致不同的結構

),為此，加上平衡演算法後產生平衡二元樹，又稱B-樹

#B-樹：在B 樹的基礎上，加上平衡演算法，多路搜尋樹，

1.每個結點儲存M/ 2到M個關鍵字，

2.非葉子結點儲存指向關鍵字範圍的子結點；############3.所有關鍵字在整顆樹中出現，且只出現一次，############4.葉子節點，非葉子結點都可以命中（是否存了資料）；###### #

B+樹：在B-樹基礎上，

1.為葉子結點增加鍊錶指標

##2.所有關鍵字都在葉子結點中出現，

3.非葉子結點作為葉子結點的索引；

4. B+樹總是到葉子結點才命中；

##B*樹：
在B+樹基礎上，為

非葉子結點也增加鍊錶指標

，將結點的最低利用率從1 /2提高到2/3;

 問題：B*效率高了，但覺為什麼b*樹用的比較少呢？ ????或哪裡有用嗎？ ？ 可能還是見的太少了。 。有了解的童鞋可以互相學習下，敬請賜教，在這裡先謝謝啦~#解答：最近得知，有個叫

Reiser4的檔案系統

好像使用到了這種結構。其作者Hans Reiser，

因為老婆讓他帶了綠帽子，就把老婆殺了，蹲大牢了，直接影響到了專案進度。 。 。 #########################

介紹：

Linux檔案系統ReiserFS作者Hans Reiser因謀殺妻子被判入獄15年後，ReiserFS的開發並沒有停止，雖然它至今沒有合併到Linux主支。一小群開發者仍在繼續開發ReiserFS的第四個版本（簡稱Reiser4），他們上個月發布了新版本，支援Linux3.5.4核心。

以上就是Mysql-索引-BTree類型【精簡】的內容，更多相關內容請關注PHP中文網（www.php.cn）！

##########