資料庫---索引的底層原理

索引的底層原理

MYSQL支援兩種索引，B+樹索引，哈希表索引；

存儲引擎為MYISAM和INNODB的索引結構：

1. MYISAM存儲引擎—主鍵索引（非聚集索引）

MYISAM引擎使用B+ 樹作為索引結構、葉節點的data域存放的是資料記錄位址；

MYISAM中，主索引和輔助索引在結構上沒有任何差別，隻是主索引要求key是唯一的，而輔助索引的key可以重複。

按照B+ 樹搜尋算法搜尋索引，如果指定的key存在，則取出其data域的值，然後以data域的值為位址，讀取相應資料記錄。

1. INNoDB存儲引擎—主鍵索引（聚集索引）

INNoDB存儲引擎的主鍵索引，葉子節點中，索引關鍵字和資料是在一起存放的。索引關鍵字和資料一起存儲在葉子節點上。支援基于B- 樹的索引結構（mysql采用的B+ 樹索引結構）

B-樹是一種m階平衡樹，葉子節點都在同一層，由于每一個節點存儲的資料量比較大，索引整個B-樹的層數是非常低的，基本上不超過三層。

由于磁盤的讀取也是按block塊操作的（記憶體是按page頁面操作的），是以B-樹的節點大小一般設定為和磁盤塊大小一緻，這樣一個B-樹節點，就可以通過一次磁盤I/O把一個磁盤塊的資料全部存儲下來，是以當使用B-樹存儲索引的時候，磁盤I/O的操作次數是最少的（MySQL的讀寫效率，主要集中在磁盤I/O上）。

1. INNODB存儲索引—輔助索引

INNODB的輔助索引，葉子節點上存放的是索引關鍵字和對應的主鍵，輔助索引的B+樹，先根據關鍵字找到對應的主鍵，再去主鍵索引樹上找到對應的行記錄資料。從索引樹可以看到，INNODB的索引關鍵字和資料都是一起存放的，展現在磁盤存儲上。

例如:建立一個user表，在磁盤上隻存儲兩種結構，user.frm:存儲表的結構，user.idb：存儲索引和資料。

MYSQL預設存儲引擎：INNoDB；

那麼MySQL最終為什麼要采用B+樹存儲索引結構呢，那麼看看B-樹和B+樹在存儲結構上有什麼不同？

1、B-樹的每一個節點，存了關鍵字和對應的資料位址，而B+樹的非葉子節點隻存關鍵字，不存資料位址。 是以B+樹的每一個非葉子節點存儲的關鍵字是遠遠多于B-樹的，B+樹的葉子節點存放關鍵字和資料， 是以，從樹的高度上來說，B+樹的高度要小于B-樹，使用的磁盤I/O次數少， 是以查詢會更快一些。

2、B-樹由于每個節點都存儲關鍵字和資料，是以離根節點近的資料，查詢的就快，離根節點遠的資料，查詢的就慢； B+樹所有的資料都存在葉子節點上，是以在B+樹上搜尋關鍵字，找到對應資料的時間是比較平均的，沒有快慢之分。

3、在B-樹上如果做區間查找，周遊的節點是非常多的；B+樹所有葉子節點被連接配接成了有序連結清單結構，是以做整表周遊和區間查找是非常容易的。 哈希索引當然是由哈希表實作的，哈希表對資料并不排序，是以不适合做區間查找，效率非常低，需要搜尋整個哈希表結構。

（MySQL底層的資料結構這裡了解的還不清晰）