索引數據結構

1、 二叉搜索樹(Binary Search Tree)

二叉搜索樹是每個節點最多有兩個子節點的樹，按照右側子節點大于本節點，左側子節點小于本節點的規律排列，可以用作搜索，結構如下圖所示

二叉樹雖然可以用于查找，但在某種特定情況下查找效率并不高，類似于下圖：

2、紅黑樹

對于二叉樹的缺點，紅黑樹是一種擁有 自平衡 屬性的二叉樹，紅黑樹有五個特性：

每個結點是黑色或者紅色。

根結點是黑色。

每個葉子結點(NIL)是黑色。 [ 注意 ：這里葉子結點，是指為空(NIL或NULL)的葉子結點！不是有值的最后一個節點。]

不能有兩個相連的紅色節點。

每個結點到葉子結點NIL所經過的黑色結點的個數一樣的。

根據以上五種屬性，紅黑樹生成時采用左旋，右旋，左右旋，右坐旋等才做，會生成出一顆相對平衡的二叉樹，如下圖

3、Hash表

Hash表類似于java中的hashMap，把索引列做hash映射后以KV結構存儲在內存中，是精準查找最快的索引結構，只需要一次hash便可以定位，但不支持范圍查找。

就是個K-V結構，不畫圖了

4、B-Tree

由于數據庫要存儲大量的數據，如果采用二叉樹進行查找，數據量過大時二叉樹的層級過多，需要由上到下進行查找效率過慢，所以出現了B-Tree，BTree有如下特征

·葉節點具有相同的深度

·葉節點的指針為空

·所有索引元素不重復

·節點中的數據索引從左到右遞增排列

數據結構直接上圖

5、B+Tree

不過mysql真正采用的不是BTree，Btree在做索引的時候有些地方并不是很實用，最終優化出了B+tree作為mysql innoDB存儲類型的索引，B+tree的特征如下

非葉子節點不存儲data，只存儲索引(冗余)

可以放更多的索引

葉子節點包含所有索引字段

葉子節點用指針連接，提高區間訪問的性能

結構如下圖

PS： innoDB中的主鍵索引的B+tree是聚集索引，葉子結點直接存儲的其他字段的值，用于減少IO的次數，而輔助索引的葉子結點則是存儲的主鍵的值，用于輔助查找

mysql主要索引類型

1：MyISAM存儲引擎索引實

MyISAM的索引和數據文件是分開的(非聚集索引)，索引的葉子節點存儲的是數據的物理地址，查找到相關索引后再用索引去硬盤上查找數據

2：InnoDB存儲引擎索引實現

InnoDB的索引是和數據存儲在一起的(聚集索引)，葉子結點中存儲了所有其他字段的值，只需要一次加載葉子結點的IO進行索引匹配，匹配成功后不需要再次進行IO操作讀取對應的數據

--表數據文件本身就是按B+Tree組織的一個索引結構文件

--非主鍵索引結構葉子節點存儲主鍵值的原因是為了一致性和節省存儲空間

3： 聯合索引的底層存儲結構

聯合索引是根據索引建立時字段的排列順序建立的索引，后續索引是對第一個字段索引的再劃分，差找時如果不能保證按照索引簡歷時的順序進行查詢，則聯合索引失效

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的mysql+零时数据结构,MySql主要索引数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。