原标題：mysql索引類型介紹
mysql索引的資料結構是樹，常用的存儲引擎innodb采用的是B+Tree。這裡對B+Tree及其相關的
查找樹進行簡要介紹。
二、各種查找樹
1、二叉排序樹(也稱為二叉查找樹)
二叉排序樹是最簡單的查找樹，特點：
a)是一棵二叉樹;
b)左子樹所有結點的值小于它的父結點的值，右子樹所有結點的值大于它的父結點的值。
2、平衡二叉樹(又稱AVL樹)
平衡二叉樹是二叉排序樹的基礎上，對樹的深度進行了限制，進而減少了查找比較的次數，
a)是一棵二叉樹;
b)左子樹所有結點的值小于它的父結點的值，右子樹所有結點的值大于它的父結點的值;
c)左子樹與右子樹的深度差在-1、0、1内，否則對子樹進行旋轉調整。
3、B-樹(B-Tree)
B-樹是多路平衡查找樹，相對于平衡二叉樹，對父結點的直接子結點個數，不再僅限于2，
可以指定m(自定義)，這樣可以在樹的深度不大量增加的前提下，儲存更多的結點。
B-樹是通常在檔案系統中使用。
特點：
a)樹的每個結點最多有m(自定義)子結點;
b)若根結點不是葉子結點，則至少有兩個子結點;
c) 除根結點外的所有非葉子結點，至少有m/2上取整個子結點;
d)父結點下的最左邊子樹所有結點的值均小于父結點最小值，
最右邊子樹所有結點的值均大于父結點最大值，
其餘中間子樹所有結點的值則介于指針的父結點兩邊的值;
e)所有葉子結點都在同一層;
注意：所有結點均帶有值
4、B+樹(B+Tree)
B+樹是B-樹變體，相對于B-樹，葉子結點的值包含了所有的值，所有父結點的值是重複了葉子結點的值，
父結點隻起索引查找的作用，同時所葉子結點也也構成了一條有序的連結清單。
mysql中存儲引擎為innodb的索引，采用的資料結構即是B+樹。
特點：
a)有m個子結點的父結點就有m個關鍵字;
b)所有葉子結點包含了所有關鍵字(值)，且構成由小到大的有序連結清單;
c) 所有非葉子結點起索引作用，結點僅包含子樹所有結點的最大值;
d)所有葉子結點都在同一層;
注意：葉子結點包含了所有的關鍵字(值)。
5、B*樹(B*Tree)
B*樹是B+樹的變體，相對B+樹，增加了對同一層非葉子結點的指針，即同一層非葉子結點也構成了一條連結清單。傳回搜狐，檢視更多
責任編輯：