索引的出現(xiàn)是為了提高查詢效率捣域，常用的主要包含三種數(shù)據(jù)結(jié)構(gòu)：哈希表沿侈、有序數(shù)組和搜索樹衣形。
哈希表
哈希表是一種以鍵 - 值（key-value）存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)翎苫，我們只要輸入待查找的值即 key嘉抒，就可以找到其對應(yīng)的值即 Value零聚。把值放在數(shù)組里，用一個(gè)哈希函數(shù)把 key 換算成一個(gè)確定的位置些侍，然后把 value 放在數(shù)組的這個(gè)位置隶症。
希表這種結(jié)構(gòu)適用于只有等值查詢的場景。
有序數(shù)組
有序數(shù)組在等值查詢和范圍查詢場景中的性能就都非常優(yōu)秀岗宣。有序數(shù)組索引只適用于靜態(tài)存儲(chǔ)引擎蚂会。
搜索樹
二叉搜索樹的特點(diǎn)是：每個(gè)節(jié)點(diǎn)的左兒子小于父節(jié)點(diǎn)，父節(jié)點(diǎn)又小于右兒子耗式。樹可以有二叉胁住，也可以有多叉。多叉樹就是每個(gè)節(jié)點(diǎn)有多個(gè)兒子刊咳，兒子之間的大小保證從左到右遞增彪见。二叉樹是搜索效率最高的，但是實(shí)際上大多數(shù)的數(shù)據(jù)庫存儲(chǔ)卻并不使用二叉樹娱挨。其原因是余指，索引不止存在內(nèi)存中，還要寫到磁盤上跷坝。
主鍵索引的葉子節(jié)點(diǎn)存的是整行數(shù)據(jù)酵镜。在 InnoDB 里，主鍵索引也被稱為聚簇索引（clustered index）探孝。
非主鍵索引的葉子節(jié)點(diǎn)內(nèi)容是主鍵的值笋婿。在 InnoDB 里誉裆，非主鍵索引也被稱為二級索引（secondary index）顿颅。
如果語句是 select * from T where ID=500，即主鍵查詢方式足丢，則只需要搜索 ID 這棵 B+ 樹粱腻；
如果語句是 select * from T where k=5庇配，即普通索引查詢方式，則需要先搜索 k 索引樹绍些，得到 ID 的值為 500捞慌，再到 ID 索引樹搜索一次。這個(gè)過程稱為回表柬批。
