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 樹，增加了對同一層非葉結點的指針，即同一層非葉子結點也構成了一條鍊錶。

三、總結

綜上，上述各種查找樹是相互關聯的。

歸結到mysql中innodb索引，採用的是B 樹，如聚集索引，是透過主鍵來聚集數據，採用B 樹實現，

這即是一種索引，也是mysql的一種資料儲存結構，葉子結點包含了所有的數據，非葉子結點僅起索引作用（若

沒有定義主鍵，則innodb會隱式定義一個主鍵來作為叢集索引）。

更多MySQL的相關技術文章，請造訪MySQL教學欄位學習！

以上是mysql索引的資料結構是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！