從最初的問(wèn)題出發(fā)，mysql是用來(lái)存儲(chǔ)&&查詢數(shù)據(jù)的越锈，索引是用來(lái)加速數(shù)據(jù)查詢過(guò)程的产园。如果讓我們?cè)O(shè)計(jì)一個(gè)數(shù)據(jù)存儲(chǔ)系統(tǒng)，我們?nèi)绾稳?shí)現(xiàn)滔驶？
1--數(shù)組 or 鏈表
最簡(jiǎn)單的想法是直接用數(shù)組存儲(chǔ)所需的數(shù)據(jù)，但是會(huì)存在插入新元素會(huì)導(dǎo)致大量元素后移的操作卿闹，費(fèi)時(shí)費(fèi)力揭糕；并且查找元素，數(shù)組和鏈表都需要粗暴的遍歷锻霎，不可戎恰；由此可想到二叉搜索樹(shù)
2--二叉搜索樹(shù)? BST
二叉搜索樹(shù)旋恼，又叫二叉排序樹(shù)吏口、二叉查找樹(shù)，極端情況下會(huì)退化為鏈表、樹(shù)高度不可控产徊，pass
3--平衡二叉樹(shù)AVL
AVL是最早發(fā)明的自平衡二叉搜索樹(shù)：
1.本身首先是一棵二叉搜索樹(shù)昂勒。
2.帶有平衡條件：每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差的絕對(duì)值（平衡因子）最多為1。
也就是說(shuō)舟铜，AVL樹(shù)戈盈，本質(zhì)上是帶了平衡功能的二叉查找樹(shù)（二叉排序樹(shù)，二叉搜索樹(shù)）谆刨。通過(guò)左旋和右旋實(shí)現(xiàn)左右子樹(shù)深度差不超過(guò)1塘娶，避免了二叉樹(shù)的極端情況的出現(xiàn)。
為什么不使用AVL作為索引：浪費(fèi)空間痊夭，具體原因如下：
Innodb存儲(chǔ)引擎的存儲(chǔ)單位是 頁(yè)（page）刁岸，1頁(yè)的大小是16kb，1頁(yè)就是樹(shù)的1個(gè)結(jié)點(diǎn)她我，而每查詢一次結(jié)點(diǎn)就要進(jìn)行一次IO操作虹曙；如果使用平衡二叉樹(shù)，一個(gè)結(jié)點(diǎn)存儲(chǔ)的信息大小遠(yuǎn)達(dá)不到16kb鸦难，太浪費(fèi)空間根吁；AVL樹(shù)存在的最大問(wèn)題就是空間利用不足，浪費(fèi)了大量空間合蔽，數(shù)據(jù)量大的時(shí)候就會(huì)成為一顆瘦高的樹(shù)击敌，樹(shù)越高，IO次數(shù)越多拴事。
4--B樹(shù)（B-樹(shù)沃斤、多路平衡查找樹(shù)）
由AVL樹(shù)的缺點(diǎn)可想到改進(jìn)方向：樹(shù)越矮胖越好，這樣IO次數(shù)就少刃宵，但是為什么用B+樹(shù)而不是用B樹(shù)衡瓶？是因?yàn)锽+樹(shù)對(duì)B樹(shù)進(jìn)行了改進(jìn)：
1）根節(jié)點(diǎn)、枝結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)牲证，只有葉子結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)哮针，這樣每個(gè)結(jié)點(diǎn)可以保存更多的關(guān)鍵字，一次磁盤(pán)IO可以加載更多的關(guān)鍵字坦袍；
2）掃表能力更強(qiáng)：葉子結(jié)點(diǎn)存儲(chǔ)了相鄰葉子結(jié)點(diǎn)的指針形成了鏈表十厢，葉子結(jié)點(diǎn)數(shù)據(jù)天然有序，直接遍歷結(jié)點(diǎn)即可獲取所有數(shù)據(jù)捂齐，無(wú)需像B樹(shù)一樣遍歷整棵樹(shù)蛮放；
3）效率穩(wěn)定，B樹(shù)每次獲取數(shù)據(jù)的深度不一定奠宜，而B(niǎo)+樹(shù)每次都需要到葉子結(jié)點(diǎn)包颁，效率和時(shí)間消耗穩(wěn)定可預(yù)估瞻想；
