一、mysql索引結構

B+樹：

B樹是?個平衡的多叉樹，一個節(jié)點可以有多個數(shù)據(jù)內容,這樣就不會出現(xiàn)二叉樹那樣數(shù)據(jù)龐大的時候,樹的高度比較高的情況,查詢的次數(shù)就會少，B+樹葉子節(jié)點間有指針相互鏈接,并且會維護了索引的順序的,所以有順序、有相鄰的引用,這樣在執(zhí)行范圍查找的時候,就可以左右移動,范圍查找的效率就會高很多。所以數(shù)據(jù)龐大的時候，B+樹被?泛使用,數(shù)據(jù)庫、?件系統(tǒng)等場景。

哈希索引：

哈希索引就是采??定的哈希算法，把鍵值換算成新的哈希值，檢索時不需要類似B+樹那樣從根節(jié)點到葉?節(jié)點逐級查找，只需?次哈希算法即可?刻定位到相應的位置，速度?常快。

如果是等值查詢，那么哈希索引明顯有絕對優(yōu)勢，因為只需要經(jīng)過?次算法即可找到相應的鍵值；

前提是鍵值都是唯?的。如果鍵值不是唯?的，就需要先找到該鍵所在位置，然后再根據(jù)鏈表往后掃描，直 到找到相應的數(shù)據(jù)；

如果是范圍查詢檢索，這時候哈希索引就毫??武之地了，因為原先是有序的鍵值，經(jīng)過哈希算法后，有可能變成不連續(xù)的了，就沒辦法再利?索引完成范圍查詢檢索；

哈希索引也沒辦法利?索引完成排序，以及l(fā)ike ‘xxx%’ 這樣的部分模糊查詢（這種部分模糊查詢，其實本質上也是范圍查詢）；

在有?量重復鍵值情況下，哈希索引的效率也是極低的，因為存在哈希碰撞問題。

紅黑樹:

紅黑樹也可以查詢很快,都是紅黑樹在數(shù)據(jù)很多的情況下,樹的高度是很高的，所以也不用來做索引了。

普通二叉樹這就更加不行了,高度不說了,它還不會平衡。

如果123456這樣按照順序添加,1永遠是跟節(jié)點,依次增加就之后在樹的右邊加。

延伸閱讀：

二、索引及其優(yōu)缺點

索引本質：索引是數(shù)據(jù)結構。這些數(shù)據(jù)結構以某種方式指向數(shù)據(jù)，這樣可以在這些數(shù)據(jù)結構的基礎上實現(xiàn)高效查找算法。

索引是在存儲引擎實現(xiàn)的，因此每種存儲引擎的索引不一定完全相同，并且每種存儲引擎不一定支持所有類型的索引。同時存儲引擎可以定義每個表的最大索引數(shù)和最大索引長度。所有存儲引擎支持每個表至少16個索引，總索引長度至少為256字節(jié)。

優(yōu)點：

1、提高數(shù)據(jù)檢索的效率，降低數(shù)據(jù)庫的I/O成本

2、通過創(chuàng)建少數(shù)索引，可以保證數(shù)據(jù)庫表中每一行數(shù)據(jù)的少數(shù)性

3、可以加速表和表之間的連接。對于有依賴關系的子表和父表聯(lián)合查詢時，可以提高查詢速度

4、在使用分組和排序子句進行數(shù)據(jù)查詢時，可以顯著減少查詢中分組和排序的時間，降低CPU的消耗

缺點：

1、創(chuàng)建索引和維護索引要耗費時間

2、索引需要占磁盤空間，存儲在磁盤上

3、雖然索引大大提高了查詢 速度，同時也會降低更新表的速度