MySQL索引底層的實(shí)現(xiàn)，今天簡(jiǎn)單聊一聊舟扎，少講“是怎么樣”分飞，更多說(shuō)說(shuō)“為什么設(shè)計(jì)成這樣”。
問(wèn)題1. 數(shù)據(jù)庫(kù)為什么要設(shè)計(jì)索引睹限？
圖書(shū)館存了1000W本圖書(shū)譬猫，要從中找到《架構(gòu)師之路》，一本本查羡疗，要查到什么時(shí)候去染服？
于是，圖書(shū)管理員設(shè)計(jì)了一套規(guī)則：
(1)一樓放歷史類(lèi)顺囊，二樓放文學(xué)類(lèi)肌索，三樓放IT類(lèi)…
(2)IT類(lèi)，又分軟件類(lèi)特碳，硬件類(lèi)…
(3)軟件類(lèi)诚亚，又按照書(shū)名音序排序…
以便快速找到一本書(shū)。
與之類(lèi)比午乓，數(shù)據(jù)庫(kù)存儲(chǔ)了1000W條數(shù)據(jù)站宗，要從中找到name=”shenjian”的記錄，一條條查益愈，要查到什么時(shí)候去梢灭？
于是，要有索引蒸其，用于提升數(shù)據(jù)庫(kù)的查找速度敏释。
問(wèn)題2. 哈希(hash)比樹(shù)(tree)更快，索引結(jié)構(gòu)為什么要設(shè)計(jì)成樹(shù)型摸袁？
加速查找速度的數(shù)據(jù)結(jié)構(gòu)钥顽，常見(jiàn)的有兩類(lèi)：
(1)哈希，例如HashMap靠汁，查詢(xún)/插入/修改/刪除的平均時(shí)間復(fù)雜度都是O(1)蜂大；
(2)樹(shù)闽铐，例如平衡二叉搜索樹(shù)，查詢(xún)/插入/修改/刪除的平均時(shí)間復(fù)雜度都是O(lg(n))奶浦；
可以看到兄墅，不管是讀請(qǐng)求，還是寫(xiě)請(qǐng)求澳叉，哈希類(lèi)型的索引隙咸，都要比樹(shù)型的索引更快一些，那為什么成洗，索引結(jié)構(gòu)要設(shè)計(jì)成樹(shù)型呢扎瓶？
畫(huà)外音：80%的同學(xué)，面試都答不出來(lái)泌枪。
索引設(shè)計(jì)成樹(shù)形，和SQL的需求相關(guān)秕岛。
對(duì)于這樣一個(gè)單行查詢(xún)的SQL需求：
select * from t where name=”shenjian”;
確實(shí)是哈希索引更快碌燕，因?yàn)槊看味贾徊樵?xún)一條記錄。
畫(huà)外音：所以继薛，如果業(yè)務(wù)需求都是單行訪問(wèn)修壕，例如passport，確實(shí)可以使用哈希索引遏考。
但是對(duì)于排序查詢(xún)的SQL需求：
分組：group by
排序：order by
比較：<慈鸠、>
…
哈希型的索引，時(shí)間復(fù)雜度會(huì)退化為O(n)灌具，而樹(shù)型的“有序”特性青团，依然能夠保持O(log(n))?的高效率。
任何脫離需求的設(shè)計(jì)都是耍流氓咖楣。
多說(shuō)一句督笆，InnoDB并不支持哈希索引。
問(wèn)題3. 數(shù)據(jù)庫(kù)索引為什么使用B+樹(shù)诱贿？
為了保持知識(shí)體系的完整性娃肿，簡(jiǎn)單介紹下幾種樹(shù)。
第一種：二叉搜索樹(shù)
二叉搜索樹(shù)珠十，如上圖料扰，是最為大家所熟知的一種數(shù)據(jù)結(jié)構(gòu)，就不展開(kāi)介紹了焙蹭，它為什么不適合用作數(shù)據(jù)庫(kù)索引晒杈？
(1)當(dāng)數(shù)據(jù)量大的時(shí)候，樹(shù)的高度會(huì)比較高壳嚎，數(shù)據(jù)量大的時(shí)候桐智，查詢(xún)會(huì)比較慢末早；
(2)每個(gè)節(jié)點(diǎn)只存儲(chǔ)一個(gè)記錄，可能導(dǎo)致一次查詢(xún)有很多次磁盤(pán)IO说庭；
畫(huà)外音：這個(gè)樹(shù)經(jīng)常出現(xiàn)在大學(xué)課本里然磷，所以最為大家所熟知。
第二種：B樹(shù)
B樹(shù)刊驴，如上圖姿搜，它的特點(diǎn)是：
(1)不再是二叉搜索，而是m叉搜索捆憎；
(2)葉子節(jié)點(diǎn)舅柜，非葉子節(jié)點(diǎn)，都存儲(chǔ)數(shù)據(jù)躲惰；
(3)中序遍歷致份，可以獲得所有節(jié)點(diǎn)；
畫(huà)外音础拨，實(shí)在不想介紹這個(gè)特性：非根節(jié)點(diǎn)包含的關(guān)鍵字個(gè)數(shù)j滿足氮块，(┌m/2┐)-1 <= j <= m-1，節(jié)點(diǎn)分裂時(shí)要滿足這個(gè)條件诡宗。
B樹(shù)被作為實(shí)現(xiàn)索引的數(shù)據(jù)結(jié)構(gòu)被創(chuàng)造出來(lái)滔蝉，是因?yàn)樗軌蛲昝赖睦谩熬植啃栽怼薄?/p>
什么是局部性原理？
局部性原理的邏輯是這樣的：
(1)內(nèi)存讀寫(xiě)塊塔沃，磁盤(pán)讀寫(xiě)慢蝠引，而且慢很多；
(2)磁盤(pán)預(yù)讀：磁盤(pán)讀寫(xiě)并不是按需讀取蛀柴，而是按頁(yè)預(yù)讀螃概，一次會(huì)讀一頁(yè)的數(shù)據(jù)，每次加載更多的數(shù)據(jù)名扛，如果未來(lái)要讀取的數(shù)據(jù)就在這一頁(yè)中谅年，可以避免未來(lái)的磁盤(pán)IO，提高效率肮韧；
畫(huà)外音：通常融蹂，一頁(yè)數(shù)據(jù)是4K。
(3)局部性原理：軟件設(shè)計(jì)要盡量遵循“數(shù)據(jù)讀取集中”與“使用到一個(gè)數(shù)據(jù)弄企，大概率會(huì)使用其附近的數(shù)據(jù)”超燃，這樣磁盤(pán)預(yù)讀能充分提高磁盤(pán)IO；
B樹(shù)為何適合做索引拘领？
(1)由于是m分叉的意乓，高度能夠大大降低；
(2)每個(gè)節(jié)點(diǎn)可以存儲(chǔ)j個(gè)記錄约素，如果將節(jié)點(diǎn)大小設(shè)置為頁(yè)大小届良，例如4K笆凌，能夠充分的利用預(yù)讀的特性，極大減少磁盤(pán)IO士葫；
第三種：B+樹(shù)
B+樹(shù)乞而，如上圖，仍是m叉搜索樹(shù)慢显，在B樹(shù)的基礎(chǔ)上爪模，做了一些改進(jìn)：
(1)非葉子節(jié)點(diǎn)不再存儲(chǔ)數(shù)據(jù)，數(shù)據(jù)只存儲(chǔ)在同一層的葉子節(jié)點(diǎn)上荚藻；
畫(huà)外音：B+樹(shù)中根到每一個(gè)節(jié)點(diǎn)的路徑長(zhǎng)度一樣屋灌，而B(niǎo)樹(shù)不是這樣。
(2)葉子之間应狱，增加了鏈表共郭，獲取所有節(jié)點(diǎn)，不再需要中序遍歷疾呻；
這些改進(jìn)讓B+樹(shù)比B樹(shù)有更優(yōu)的特性：
(1)范圍查找落塑，定位min與max之后，中間葉子節(jié)點(diǎn)罐韩，就是結(jié)果集，不用中序回溯污朽；
畫(huà)外音：范圍查詢(xún)?cè)赟QL中用得很多散吵，這是B+樹(shù)比B樹(shù)最大的優(yōu)勢(shì)。
(2)葉子節(jié)點(diǎn)存儲(chǔ)實(shí)際記錄行蟆肆，記錄行相對(duì)比較緊密的存儲(chǔ)矾睦，適合大數(shù)據(jù)量磁盤(pán)存儲(chǔ)；非葉子節(jié)點(diǎn)存儲(chǔ)記錄的PK炎功，用于查詢(xún)加速枚冗，適合內(nèi)存存儲(chǔ)；
(3)非葉子節(jié)點(diǎn)蛇损，不存儲(chǔ)實(shí)際記錄赁温，而只存儲(chǔ)記錄的KEY的話，那么在相同內(nèi)存的情況下淤齐，B+樹(shù)能夠存儲(chǔ)更多索引股囊；
最后，量化說(shuō)下更啄，為什么m叉的B+樹(shù)比二叉搜索樹(shù)的高度大大大大降低稚疹？
大概計(jì)算一下：
(1)局部性原理老充，將一個(gè)節(jié)點(diǎn)的大小設(shè)為一頁(yè)娶吞，一頁(yè)4K，假設(shè)一個(gè)KEY有8字節(jié)，一個(gè)節(jié)點(diǎn)可以存儲(chǔ)500個(gè)KEY窘拯，即j=500
(2)m叉樹(shù)，大概m/2<= j <=m盛险，即可以差不多是1000叉樹(shù)
(3)那么：
一層樹(shù)：1個(gè)節(jié)點(diǎn)妓柜，1*500個(gè)KEY，大小4K
二層樹(shù)：1000個(gè)節(jié)點(diǎn)偎行，1000*500=50W個(gè)KEY川背，大小1000*4K=4M
三層樹(shù)：1000*1000個(gè)節(jié)點(diǎn)，1000*1000*500=5億個(gè)KEY蛤袒，大小1000*1000*4K=4G
畫(huà)外音：額熄云，幫忙看下有沒(méi)有算錯(cuò)。
可以看到妙真，存儲(chǔ)大量的數(shù)據(jù)（5億）缴允，并不需要太高樹(shù)的深度（高度3），索引也不是太占內(nèi)存（4G）珍德。
總結(jié)
數(shù)據(jù)庫(kù)索引用于加速查詢(xún)
雖然哈希索引是O(1)练般，樹(shù)索引是O(log(n))，但SQL有很多“有序”需求锈候，故數(shù)據(jù)庫(kù)使用樹(shù)型索引
InnoDB不支持哈希索引
數(shù)據(jù)預(yù)讀的思路是：磁盤(pán)讀寫(xiě)并不是按需讀取薄料，而是按頁(yè)預(yù)讀，一次會(huì)讀一頁(yè)的數(shù)據(jù)泵琳，每次加載更多的數(shù)據(jù)摄职，以便未來(lái)減少磁盤(pán)IO
局部性原理：軟件設(shè)計(jì)要盡量遵循“數(shù)據(jù)讀取集中”與“使用到一個(gè)數(shù)據(jù)，大概率會(huì)使用其附近的數(shù)據(jù)”获列，這樣磁盤(pán)預(yù)讀能充分提高磁盤(pán)IO
數(shù)據(jù)庫(kù)的索引最常用B+樹(shù)：
(1)很適合磁盤(pán)存儲(chǔ)谷市，能夠充分利用局部性原理，磁盤(pán)預(yù)讀击孩；
(2)很低的樹(shù)高度迫悠，能夠存儲(chǔ)大量數(shù)據(jù)；
(3)索引本身占用的內(nèi)存很泄摇创泄；
(4)能夠很好的支持單點(diǎn)查詢(xún)，范圍查詢(xún)括蝠，有序性查詢(xún)验烧；
