網絡上看了很多關于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）！
