根據(jù)文章MySQL索引詳解（三）索引的底層原理，了解了MySQL的索引實(shí)現(xiàn)原理，那么為什么在眾多的數(shù)據(jù)結(jié)構(gòu)中吊履，索引的實(shí)現(xiàn)選中了BTree（實(shí)際實(shí)現(xiàn)是B+Tree，此文中不做詳細(xì)區(qū)分）调鬓，而不是二叉樹(shù)艇炎，AVL樹(shù)，紅黑樹(shù)等其他的數(shù)據(jù)結(jié)構(gòu)呢袖迎？
文章將根據(jù)以下的目錄結(jié)構(gòu)進(jìn)行講解
文章目錄結(jié)構(gòu)
1冕臭、BTree與其他數(shù)據(jù)結(jié)構(gòu)的比較
2腺晾、BTree做索引結(jié)構(gòu)的根本原因
1燕锥、BTree與其他數(shù)據(jù)結(jié)構(gòu)的比較
二叉樹(shù)
先從最簡(jiǎn)單的樹(shù)二叉樹(shù)說(shuō)起。二叉樹(shù)的要求是左子樹(shù)的鍵值小于根的鍵值小于右子樹(shù)的鍵值悯蝉。
結(jié)構(gòu)如下圖：
二叉樹(shù)的問(wèn)題是归形，如果插入順序是有序的，那么樹(shù)形結(jié)構(gòu)有可能會(huì)變得很深鼻由，甚至退化成一個(gè)鏈表結(jié)構(gòu)暇榴，這樣查找的效率會(huì)變的非常低厚棵。如下圖：
AVL樹(shù)
AVL樹(shù)是（Adelson-Velskii和Landis樹(shù)）自平衡二叉查找樹(shù)，AVL樹(shù)的要求是任何兩個(gè)子樹(shù)的高度差不超過(guò)1蔼紧。結(jié)構(gòu)如下圖：
這樣的要求就不會(huì)出現(xiàn)上面二叉樹(shù)退化為鏈表的結(jié)構(gòu)婆硬。但是AVL樹(shù)每次插入的時(shí)候都需要通過(guò)各種旋轉(zhuǎn)操作，使自身變的平衡（左右子樹(shù)高度差不大于1）奸例。這樣的樹(shù)形結(jié)構(gòu)雖然 查詢速度比較彬犯，但是插入的過(guò)程相對(duì)較慢。
廣泛的使用與windos NT內(nèi)核中
紅黑樹(shù)
AVL數(shù)是一種嚴(yán)格的平衡二叉樹(shù)查吊，每次插入或刪除操作都需要嚴(yán)格的檢測(cè)然后進(jìn)行調(diào)整結(jié)構(gòu)谐区。嚴(yán)重的影響了插入刪除的性能。而紅黑樹(shù)為了優(yōu)化插入和刪除的性能逻卖，不嚴(yán)格要求平衡宋列，屬于一種弱平衡二叉樹(shù)。紅黑樹(shù)要求：沒(méi)有一條路徑比其他路徑長(zhǎng)超過(guò)2倍评也。
BTree
為了考慮存儲(chǔ)的問(wèn)題炼杖，如果一個(gè)節(jié)點(diǎn)只能擁有兩個(gè)子節(jié)點(diǎn)，那么存儲(chǔ)的數(shù)據(jù)量是遠(yuǎn)遠(yuǎn)不夠的盗迟。所以設(shè)計(jì)出可以擁更多子節(jié)點(diǎn)的BTree嘹叫。
2、BTree做索引結(jié)構(gòu)的根本原因
因?yàn)閿?shù)據(jù)的存儲(chǔ)在硬盤而不是內(nèi)存诈乒，所有BTree的設(shè)計(jì)是為磁盤和其他外部存儲(chǔ)所設(shè)計(jì)罩扇。
定義使用硬盤上的一個(gè)磁盤塊來(lái)存儲(chǔ)一個(gè)BTree數(shù)的節(jié)點(diǎn)。但是如果把data存放到每個(gè)節(jié)點(diǎn)中怕磨，這樣會(huì)占據(jù)磁盤塊空間喂饥，為了讓固定大小的磁盤塊上可以存放更多的鍵值，對(duì)BTree進(jìn)行了一下優(yōu)化肠鲫，得到了B+Tree员帮。結(jié)構(gòu)如下：
與BTree不同的地方在于，將每個(gè)非葉子節(jié)點(diǎn)中的data去掉导饲，并且給葉子節(jié)點(diǎn)增加一個(gè)雙向的指針捞高。這樣做的好處是，每個(gè)節(jié)點(diǎn)中可以存放更多的索引鍵渣锦，減小樹(shù)的深度硝岗，提升查找速度。
增加葉子節(jié)點(diǎn)的雙向指針袋毙，用于節(jié)點(diǎn)的遍歷型檀。
3、使用B樹(shù)和B+樹(shù)構(gòu)建索引各自的好處
使用B樹(shù)的好處
B樹(shù)可以在內(nèi)部節(jié)點(diǎn)同時(shí)存儲(chǔ)鍵和值听盖，因此胀溺，把頻繁訪問(wèn)的數(shù)據(jù)放在靠近根節(jié)點(diǎn)的地方將會(huì)大大提高熱點(diǎn)數(shù)據(jù)的查詢效率裂七。這種特性使得B樹(shù)在特定數(shù)據(jù)重復(fù)多次查詢的場(chǎng)景中更加高效。
使用B+樹(shù)的好處
由于B+樹(shù)的內(nèi)部節(jié)點(diǎn)只存放鍵仓坞，不存放值背零，因此，一次讀取无埃，可以在內(nèi)存頁(yè)中獲取更多的鍵捉兴，有利于更快地縮小查找范圍。B+樹(shù)的葉節(jié)點(diǎn)由一條鏈相連录语，因此倍啥，當(dāng)需要進(jìn)行一次全數(shù)據(jù)遍歷的時(shí)候，B+樹(shù)只需要使用O(logN)時(shí)間找到最小的一個(gè)節(jié)點(diǎn)澎埠，然后通過(guò)鏈進(jìn)行O(N)的順序遍歷即可虽缕。而B(niǎo)樹(shù)則需要對(duì)樹(shù)的每一層進(jìn)行遍歷，這會(huì)需要更多的內(nèi)存置換次數(shù)蒲稳，因此也就需要花費(fèi)更多的時(shí)間
