Mysql索引數(shù)據(jù)結(jié)構(gòu)

?????? Hash表與B+樹

?????? 樹的查詢效率高O(log N)，可以保持基本有序。

B-樹（B樹）實現(xiàn)細節(jié)

?????? 磁盤IO消耗時間比較長，數(shù)據(jù)庫索引存儲在磁盤上，數(shù)據(jù)量極大的時候，索引所占的存儲空間也是非?？捎^的。

?????? 索引查詢時，將不可能將所有的索引全部加載到內(nèi)存中，只有逐一加載每一個索引頁（即對應(yīng)B樹中的節(jié)點）。

索引查找時，最壞條件下的IO次數(shù)即為索引樹的高度。

為了減少磁盤IO的次數(shù)，需要把高瘦的樹結(jié)構(gòu)變得矮胖。這就是B-樹的特征之一。

B樹是一種多路平衡查找樹，他的每一個節(jié)點最多包含K個孩子，K即位B樹的階。K的大小取決于磁盤頁的大小。

B-樹的特征：(m階)

1.? ?根節(jié)點至少有兩個子女。

2.? ?每個中間節(jié)點都包含k-1個元素和k個孩子。其中m/2 <= k <= m

3.? ? 每一個葉子節(jié)點都包含k-1個元素，其中m/2 <= k <= m

4.? ? 所有的葉子節(jié)點都位于同一層。

5.? ? 每個節(jié)點中的元素從小到大排列，節(jié)點當中k-1個元素正好是k個孩子包含的元素的值域分劃

B+樹

?????? B+樹是B樹的一種變體，有著比B樹更高的查詢性能。

M階的B樹有以下特征:

[if !supportLists]1.????[endif]有K個子樹的中間節(jié)點含有K個元素（B樹中是K-1個），每個元素不包含數(shù)據(jù)，只用來索引，所有的數(shù)據(jù)都包含在葉子節(jié)點中。

[if !supportLists]2.????[endif]所有的葉子節(jié)點包含了全部元素的信息，及指向包含這些元素記錄的指針。且葉子節(jié)點本身依照關(guān)鍵字的大小自小而大，順序排列。

[if !supportLists]3.????[endif]所有的中間節(jié)點元素都同時存在與子節(jié)點，在子節(jié)點中是最大（或最小的元素）。

根節(jié)點中的最大元素，代表整個樹中的最大元素。

衛(wèi)星數(shù)據(jù)：索引元素所指向的數(shù)據(jù)記錄。在數(shù)據(jù)庫中的某一行，在B樹中，無論是中間節(jié)點還是葉子節(jié)點，都帶有衛(wèi)星數(shù)據(jù)。

需要補充的是，在數(shù)據(jù)庫的聚集索引（Clustered

Index）中，葉子節(jié)點直接包含衛(wèi)星數(shù)據(jù)。在非聚集索引（NonClustered Index）中，葉子節(jié)點帶有指向衛(wèi)星數(shù)據(jù)的指針。

在B+樹中，中間節(jié)點不含有衛(wèi)星數(shù)據(jù)，同樣大小的磁盤頁，可以包含更多的節(jié)點指針。IO次數(shù)更少。

B+樹的查詢必須查到葉子節(jié)點，而B-樹只需要查到所查元素即可。

B-樹的查找性能不穩(wěn)定，B+樹的每一次查找性能都是穩(wěn)定的。

B-樹的范圍查找采用中序遍歷，性能不好。B+樹先找到邊界，然后進行鏈表操作，性能高。

B-樹與B+樹的插入刪除操作大體一致。

B+樹的特征：

1.有k個子樹的中間節(jié)點包含有k個元素（B樹中是k-1個元素），每個元素不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點。

2.所有的葉子結(jié)點中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接。

3.所有的中間節(jié)點元素都同時存在于子節(jié)點，在子節(jié)點元素中是最大（或最小）元素。

B+樹的優(yōu)勢：

1.單一節(jié)點存儲更多的元素，使得查詢的IO次數(shù)更少。

2.所有查詢都要查找到葉子節(jié)點，查詢性能穩(wěn)定。

3.所有葉子節(jié)點形成有序鏈表，便于范圍查詢。