鏈表 -> 二叉查找樹 -> 平衡二叉樹 -> B樹 -> B+樹
鏈表：層級等于鏈表長度
二叉查找樹：鏈表優(yōu)化时肿，左子節(jié)點小于當(dāng)前節(jié)點，右子節(jié)點大于當(dāng)前節(jié)點，可能不均勻憔杨，極端情況下和鏈表一樣箩朴，降低讀取磁盤次數(shù)岗喉。
平衡二叉樹：左右子節(jié)點的高度差不大于1，當(dāng)出現(xiàn)大于1時炸庞，自動進(jìn)行平衡調(diào)整钱床，降低讀取磁盤次數(shù)
B數(shù)（平衡樹）：針對二叉樹只能存儲一個鍵值對的情況進(jìn)行優(yōu)化，每個節(jié)點可以存儲多個鍵值對埠居，每個節(jié)點擁有更多的子節(jié)點查牌。此節(jié)點也稱為頁（磁盤塊），mysql數(shù)據(jù)的存取以頁為單位滥壕，降低磁盤次數(shù)纸颜。
B+樹：
- 非葉子節(jié)點不存數(shù)據(jù)，僅存儲鍵值绎橘。InnoDB默認(rèn)大小為16KB胁孙。這樣可以存儲更多的鍵值，進(jìn)一步提升效率称鳞。假設(shè)每個節(jié)點存1000個鍵涮较，即1000階。如有三層則可以存儲數(shù)據(jù)量：100010001000 = 10億冈止。由于根節(jié)點常駐內(nèi)存狂票，因此10億的數(shù)據(jù)里面查找某個值僅需讀取2次磁盤IO。
- B+樹索引存儲在葉子節(jié)點熙暴，并且按順序存儲闺属。因此排序查找慌盯、范圍查找、分組查詢更簡單掂器。而B樹是數(shù)據(jù)存儲在各節(jié)點亚皂，難以實現(xiàn)。
- B+樹頁之間是雙向鏈表連接国瓮，葉子節(jié)點內(nèi)部是單向鏈表連接
聚集索引：以主鍵作為B+樹的鍵值孕讳，而構(gòu)建的B+樹索引，稱為聚集索引巍膘。葉子節(jié)點存儲行數(shù)據(jù)
非聚集索引：以非主鍵作為B+樹的鍵值厂财，而構(gòu)建的B+樹索引，稱為非聚集索引峡懈。葉子節(jié)點存儲主鍵值璃饱，查詢數(shù)據(jù)需要根據(jù)主鍵到聚集索引里查詢，稱為回表查詢
