Mysql索引數(shù)據(jù)結(jié)構(gòu)
?????? Hash表與B+樹(shù)
?????? 樹(shù)的查詢(xún)效率高O(log N)，可以保持基本有序汇歹。
B-樹(shù)（B樹(shù)）實(shí)現(xiàn)細(xì)節(jié)
?????? 磁盤(pán)IO消耗時(shí)間比較長(zhǎng)秋冰，數(shù)據(jù)庫(kù)索引存儲(chǔ)在磁盤(pán)上，數(shù)據(jù)量極大的時(shí)候插佛，索引所占的存儲(chǔ)空間也是非掣苎玻可觀(guān)的。
?????? 索引查詢(xún)時(shí)雇寇，將不可能將所有的索引全部加載到內(nèi)存中氢拥，只有逐一加載每一個(gè)索引頁(yè)（即對(duì)應(yīng)B樹(shù)中的節(jié)點(diǎn)）蚌铜。
索引查找時(shí)，最壞條件下的IO次數(shù)即為索引樹(shù)的高度嫩海。
為了減少磁盤(pán)IO的次數(shù)冬殃，需要把高瘦的樹(shù)結(jié)構(gòu)變得矮胖。這就是B-樹(shù)的特征之一叁怪。
B樹(shù)是一種多路平衡查找樹(shù)审葬，他的每一個(gè)節(jié)點(diǎn)最多包含K個(gè)孩子，K即位B樹(shù)的階奕谭。K的大小取決于磁盤(pán)頁(yè)的大小涣觉。
B-樹(shù)的特征：(m階)
1.? ?根節(jié)點(diǎn)至少有兩個(gè)子女。
2.? ?每個(gè)中間節(jié)點(diǎn)都包含k-1個(gè)元素和k個(gè)孩子血柳。其中m/2 <= k <= m
3.? ? 每一個(gè)葉子節(jié)點(diǎn)都包含k-1個(gè)元素官册，其中m/2 <= k <= m
4.? ? 所有的葉子節(jié)點(diǎn)都位于同一層。
5.? ? 每個(gè)節(jié)點(diǎn)中的元素從小到大排列难捌，節(jié)點(diǎn)當(dāng)中k-1個(gè)元素正好是k個(gè)孩子包含的元素的值域分劃
B+樹(shù)
?????? B+樹(shù)是B樹(shù)的一種變體膝宁，有著比B樹(shù)更高的查詢(xún)性能。
M階的B樹(shù)有以下特征:
[if !supportLists]1.????[endif]有K個(gè)子樹(shù)的中間節(jié)點(diǎn)含有K個(gè)元素（B樹(shù)中是K-1個(gè)）根吁，每個(gè)元素不包含數(shù)據(jù)员淫，只用來(lái)索引，所有的數(shù)據(jù)都包含在葉子節(jié)點(diǎn)中击敌。
[if !supportLists]2.????[endif]所有的葉子節(jié)點(diǎn)包含了全部元素的信息满粗，及指向包含這些元素記錄的指針。且葉子節(jié)點(diǎn)本身依照關(guān)鍵字的大小自小而大愚争，順序排列映皆。
[if !supportLists]3.????[endif]所有的中間節(jié)點(diǎn)元素都同時(shí)存在與子節(jié)點(diǎn)，在子節(jié)點(diǎn)中是最大（或最小的元素）轰枝。
根節(jié)點(diǎn)中的最大元素捅彻，代表整個(gè)樹(shù)中的最大元素。
衛(wèi)星數(shù)據(jù)：索引元素所指向的數(shù)據(jù)記錄鞍陨。在數(shù)據(jù)庫(kù)中的某一行步淹，在B樹(shù)中，無(wú)論是中間節(jié)點(diǎn)還是葉子節(jié)點(diǎn)诚撵，都帶有衛(wèi)星數(shù)據(jù)缭裆。
需要補(bǔ)充的是，在數(shù)據(jù)庫(kù)的聚集索引（Clustered
Index）中寿烟，葉子節(jié)點(diǎn)直接包含衛(wèi)星數(shù)據(jù)澈驼。在非聚集索引（NonClustered Index）中，葉子節(jié)點(diǎn)帶有指向衛(wèi)星數(shù)據(jù)的指針筛武。
在B+樹(shù)中缝其，中間節(jié)點(diǎn)不含有衛(wèi)星數(shù)據(jù)挎塌，同樣大小的磁盤(pán)頁(yè)，可以包含更多的節(jié)點(diǎn)指針内边。IO次數(shù)更少榴都。
B+樹(shù)的查詢(xún)必須查到葉子節(jié)點(diǎn)，而B(niǎo)-樹(shù)只需要查到所查元素即可漠其。
B-樹(shù)的查找性能不穩(wěn)定嘴高，B+樹(shù)的每一次查找性能都是穩(wěn)定的。
B-樹(shù)的范圍查找采用中序遍歷和屎，性能不好阳惹。B+樹(shù)先找到邊界，然后進(jìn)行鏈表操作眶俩，性能高。
B-樹(shù)與B+樹(shù)的插入刪除操作大體一致快鱼。
B+樹(shù)的特征：
1.有k個(gè)子樹(shù)的中間節(jié)點(diǎn)包含有k個(gè)元素（B樹(shù)中是k-1個(gè)元素）颠印，每個(gè)元素不保存數(shù)據(jù)，只用來(lái)索引抹竹，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)线罕。
2.所有的葉子結(jié)點(diǎn)中包含了全部元素的信息，及指向含這些元素記錄的指針窃判，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接钞楼。
3.所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)，在子節(jié)點(diǎn)元素中是最大（或最邪懒铡）元素询件。
B+樹(shù)的優(yōu)勢(shì)：
1.單一節(jié)點(diǎn)存儲(chǔ)更多的元素，使得查詢(xún)的IO次數(shù)更少唆樊。
2.所有查詢(xún)都要查找到葉子節(jié)點(diǎn)宛琅，查詢(xún)性能穩(wěn)定。
3.所有葉子節(jié)點(diǎn)形成有序鏈表逗旁，便于范圍查詢(xún)嘿辟。
