一华临、概念
引用百度：在關(guān)系數(shù)據(jù)庫(kù)中，索引是一種單獨(dú)的铆隘、物理的對(duì)數(shù)據(jù)庫(kù)表中一列或多列的值進(jìn)行排序的一種存儲(chǔ)結(jié)構(gòu)又沾，它是某個(gè)表中一列或若干列值的集合和相應(yīng)的指向表中物理標(biāo)識(shí)這些值的數(shù)據(jù)頁(yè)的邏輯指針清單。索引的作用相當(dāng)于圖書(shū)的目錄归露，可以根據(jù)目錄中的頁(yè)碼洲脂。
為了在mysql里查詢數(shù)據(jù)的時(shí)候提高檢索效率，縮短檢索時(shí)間剧包，mysql底層就是通過(guò)不同的存儲(chǔ)引擎根據(jù)不同的策略創(chuàng)建索引恐锦。底層的實(shí)現(xiàn)還是在不同數(shù)據(jù)結(jié)構(gòu)中尋找最合適的檢索算法去做的，所以為什么總喜歡問(wèn)一些查找算法疆液，大學(xué)里數(shù)據(jù)結(jié)構(gòu)這門(mén)課程很重要一铅。。
https://www.cnblogs.com/yw09041432/p/5908444.html

二堕油、價(jià)值
程序與計(jì)算機(jī)對(duì)抗的歷程中潘飘，對(duì)大的挑戰(zhàn)是磁盤(pán)I/O操作，最初的數(shù)據(jù)是放在文件中掉缺，當(dāng)數(shù)據(jù)量達(dá)到一定級(jí)別時(shí)福也，檢索時(shí)還是全量的效率自然會(huì)變低；數(shù)據(jù)庫(kù)慢慢演變而來(lái)攀圈，將數(shù)據(jù)分成一塊一塊的區(qū)域存儲(chǔ)暴凑，但是依然擺脫不了全量索引的問(wèn)題，所以我們必須引進(jìn)一種東西來(lái)記錄數(shù)據(jù)的位置（指針）赘来，就是索引现喳。
索引也是一種數(shù)據(jù)凯傲，假設(shè)where條件全部命中索引,那么必然會(huì)去索引文件中找到那個(gè)索引，索引文件是怎么生成的呢嗦篱？

image.png

思考：
以前有個(gè)面試官問(wèn)過(guò)我一個(gè)問(wèn)題：HashMap大小一百萬(wàn)和一個(gè)億的get效率有影響嗎冰单？大家可以思考下這個(gè)問(wèn)題。放在這里的話灸促，我們要反思下是不是有了索引就無(wú)敵了诫欠？影響索引效率的關(guān)鍵是B+樹(shù)的深度，可以這樣說(shuō)如果樹(shù)的深度不變 檢索的復(fù)雜度總是O(logn),但是在insert浴栽、delete這樣影響索引結(jié)構(gòu)的操作會(huì)造成索引樹(shù)節(jié)點(diǎn)重排荒叼，在加上是I/O寫(xiě)操作，必然非常耗時(shí)（其實(shí)也有解決的辦法）典鸡。
但是是不是select效率是不變的呢被廓？思考1ms。萝玷。嫁乘。
單機(jī)情況下似乎是的，但是想想在分布式環(huán)境下呢球碉？
從影響JVM蜓斧、內(nèi)存的角度去思考，可以引入一種新的技術(shù)redis

三睁冬、INNODB挎春、MYISAM存儲(chǔ)引擎
1、兩種存儲(chǔ)引擎的區(qū)別
用戶可以根據(jù)個(gè)人需求選擇不同的引擎作為 Mysql 數(shù)據(jù)表的底層引擎痴突，但是數(shù)據(jù)和索引到底怎么組織起來(lái)也是需要一番設(shè)計(jì)搂蜓，設(shè)計(jì)理念的不同也導(dǎo)致了 Innodb 和 Myisam 的出現(xiàn)，各自呈現(xiàn)獨(dú)特的性能辽装。
MyISAM 雖然數(shù)據(jù)查找性能極佳帮碰，但是不支持事務(wù)處理。Innodb 最大的特色就是支持了 ACID 兼容的事務(wù)功能拾积，而且他支持行級(jí)鎖殉挽。Mysql 建立表的時(shí)候就可以指定引擎：

image.png

image.png

文件結(jié)構(gòu)
Innodb 創(chuàng)建表后生成的文件有：

• frm:創(chuàng)建表的語(yǔ)句
• idb:表里面的數(shù)據(jù)+索引文件

Myisam 創(chuàng)建表后生成的文件有

• frm:創(chuàng)建表的語(yǔ)句
• MYD:表里面的數(shù)據(jù)文件（myisam data）
• MYI:表里面的索引文件（myisam index）

從生成的文件看來(lái)，這兩個(gè)引擎底層數(shù)據(jù)和索引的組織方式并不一樣拓巧，MyISAM 引擎把數(shù)據(jù)和索引分開(kāi)了斯碌，一人一個(gè)文件，這叫做非聚集索引方式肛度；Innodb 引擎把數(shù)據(jù)和索引放在同一個(gè)文件里了傻唾，這叫做聚集索引方式。

MyISAM 用的是非聚集索引方式，即數(shù)據(jù)和索引落在不同的兩個(gè)文件上冠骄。MyISAM 在建表時(shí)以主鍵作為 KEY 來(lái)建立主索引 B+樹(shù)伪煤，樹(shù)的葉子節(jié)點(diǎn)存的是對(duì)應(yīng)數(shù)據(jù)的物理地址。我們拿到這個(gè)物理地址后凛辣，就可以到 MyISAM 數(shù)據(jù)文件中直接定位到具體的數(shù)據(jù)記錄了抱既。

image.png

InnoDB 是聚集索引方式，因此數(shù)據(jù)和索引都存儲(chǔ)在同一個(gè)文件里扁誓。首先 InnoDB 會(huì)根據(jù)主鍵 ID 作為 KEY 建立索引 B+樹(shù)防泵，如左下圖所示，而 B+樹(shù)的葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵 ID 對(duì)應(yīng)的數(shù)據(jù)蝗敢，比如在執(zhí)行 select * from user_info where id=15 這個(gè)語(yǔ)句時(shí)捷泞，InnoDB 就會(huì)查詢這顆主鍵 ID 索引 B+樹(shù)，找到對(duì)應(yīng)的 user_name='Bob'前普。
這是建表的時(shí)候 InnoDB 就會(huì)自動(dòng)建立好主鍵 ID 索引樹(shù)肚邢，這也是為什么 Mysql 在建表時(shí)要求必須指定主鍵的原因壹堰。當(dāng)我們?yōu)楸砝锬硞€(gè)字段加索引時(shí) InnoDB 會(huì)怎么建立索引樹(shù)呢拭卿？比如我們要給 user_name 這個(gè)字段加索引，那么 InnoDB 就會(huì)建立 user_name 索引 B+樹(shù)贱纠，節(jié)點(diǎn)里存的是 user_name 這個(gè) KEY峻厚，葉子節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)的是主鍵 KEY。注意谆焊，葉子存儲(chǔ)的是主鍵 KEY惠桃！拿到主鍵 KEY 后，InnoDB 才會(huì)去主鍵索引樹(shù)里根據(jù)剛在 user_name 索引樹(shù)找到的主鍵 KEY 查找到對(duì)應(yīng)的數(shù)據(jù)辖试。

image.png

問(wèn)題來(lái)了辜王，為什么 InnoDB 只在主鍵索引樹(shù)的葉子節(jié)點(diǎn)存儲(chǔ)了具體數(shù)據(jù)，但是其他索引樹(shù)卻不存具體數(shù)據(jù)呢罐孝，而要多此一舉先找到主鍵呐馆，再在主鍵索引樹(shù)找到對(duì)應(yīng)的數(shù)據(jù)呢?
其實(shí)很簡(jiǎn)單，因?yàn)?InnoDB 需要節(jié)省存儲(chǔ)空間莲兢。一個(gè)表里可能有很多個(gè)索引汹来，InnoDB 都會(huì)給每個(gè)加了索引的字段生成索引樹(shù)，如果每個(gè)字段的索引樹(shù)都存儲(chǔ)了具體數(shù)據(jù)改艇，那么這個(gè)表的索引數(shù)據(jù)文件就變得非常巨大（數(shù)據(jù)極度冗余了）收班。從節(jié)約磁盤(pán)空間的角度來(lái)說(shuō)，真的沒(méi)有必要每個(gè)字段索引樹(shù)都存具體數(shù)據(jù)谒兄，通過(guò)這種看似“多此一舉”的步驟摔桦，在犧牲較少查詢的性能下節(jié)省了巨大的磁盤(pán)空間，這是非常有值得的承疲。
在進(jìn)行 InnoDB 和 MyISAM 特點(diǎn)對(duì)比時(shí)談到邻耕，MyISAM 查詢性能更好瘦穆，從上面索引文件數(shù)據(jù)文件的設(shè)計(jì)來(lái)看也可以看出原因：MyISAM 直接找到物理地址后就可以直接定位到數(shù)據(jù)記錄，但是 InnoDB 查詢到葉子節(jié)點(diǎn)后赊豌，還需要再查詢一次主鍵索引樹(shù)扛或，才可以定位到具體數(shù)據(jù)。等于 MyISAM 一步就查到了數(shù)據(jù)碘饼，但是 InnoDB 要兩步熙兔，那當(dāng)然 MyISAM 查詢性能更高。
本文首先探討了哪種數(shù)據(jù)結(jié)構(gòu)更適合作為 Mysql 底層索引的實(shí)現(xiàn)艾恼，然后再介紹了 Mysql 兩種經(jīng)典數(shù)據(jù)引擎 MyISAM 和 InnoDB 的底層實(shí)現(xiàn)住涉。最后再總結(jié)一下什么時(shí)候需要給你的表里的字段加索引吧：
1.較頻繁的作為查詢條件的字段應(yīng)該創(chuàng)建索引；
2.唯一性太差的字段不適合單獨(dú)創(chuàng)建索引钠绍，即使該字段頻繁作為查詢條件舆声；
3.更新非常頻繁的字段不適合創(chuàng)建索引。

2柳爽、索引數(shù)據(jù)結(jié)構(gòu)的選型問(wèn)題
為什么索引底層使用的是B+樹(shù)媳握？

• 哈希表（hash）
  哈希表是做數(shù)據(jù)快速檢索的有效利器。
  哈希算法：也叫散列算法磷脯，就是把任意值(key)通過(guò)哈希函數(shù)變換為固定長(zhǎng)度的 key 地址蛾找，通過(guò)這個(gè)地址進(jìn)行具體數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

  
  
  [圖片上傳中...(image.png-33cb39-1586603232629-0)]
  
  

  考慮這個(gè)數(shù)據(jù)庫(kù)表 user赵誓，表中一共有 7 個(gè)數(shù)據(jù)打毛，我們需要檢索 id=7 的數(shù)據(jù)，SQL 語(yǔ)法是：

select \* from user where id=7;

哈希算法首先計(jì)算存儲(chǔ) id=7 的數(shù)據(jù)的物理地址 addr=hash(7)=4231俩功，而 4231 映射的物理地址是 0x77幻枉，0x77 就是 id=7 存儲(chǔ)的額數(shù)據(jù)的物理地址，通過(guò)該獨(dú)立地址可以找到對(duì)應(yīng) user_name='g'這個(gè)數(shù)據(jù)诡蜓。這就是哈希算法快速檢索數(shù)據(jù)的計(jì)算過(guò)程熬甫。
但是哈希算法有個(gè)數(shù)據(jù)碰撞的問(wèn)題，也就是哈希函數(shù)可能對(duì)不同的 key 會(huì)計(jì)算出同一個(gè)結(jié)果万牺，比如 hash(7)可能跟 hash(199)計(jì)算出來(lái)的結(jié)果一樣罗珍，也就是不同的 key 映射到同一個(gè)結(jié)果了，這就是碰撞問(wèn)題脚粟。解決碰撞問(wèn)題的一個(gè)常見(jiàn)處理方式就是鏈地址法覆旱，即用鏈表把碰撞的數(shù)據(jù)接連起來(lái)。計(jì)算哈希值之后核无，還需要檢查該哈希值是否存在碰撞數(shù)據(jù)鏈表扣唱，有則一直遍歷到鏈表尾，直達(dá)找到真正的 key 對(duì)應(yīng)的數(shù)據(jù)為止。

image.png

image.png

從算法時(shí)間復(fù)雜度分析來(lái)看噪沙，哈希算法時(shí)間復(fù)雜度為 O（1）炼彪，檢索速度非常快正歼。比如查找 id=7 的數(shù)據(jù)辐马，哈希索引只需要計(jì)算一次就可以獲取到對(duì)應(yīng)的數(shù)據(jù)，檢索速度非尘忠澹快喜爷。但是 Mysql 并沒(méi)有采取哈希作為其底層算法，這是為什么呢萄唇？
因?yàn)榭紤]到數(shù)據(jù)檢索有一個(gè)常用手段就是范圍查找檩帐，比如以下這個(gè) SQL 語(yǔ)句：

select \* from user where id \>3;

針對(duì)以上這個(gè)語(yǔ)句，我們希望做的是找出 id>3 的數(shù)據(jù)另萤，這是很典型的范圍查找湃密。如果使用哈希算法實(shí)現(xiàn)的索引，范圍查找怎么做呢四敞？一個(gè)簡(jiǎn)單的思路就是一次把所有數(shù)據(jù)找出來(lái)加載到內(nèi)存泛源，然后再在內(nèi)存里篩選篩選目標(biāo)范圍內(nèi)的數(shù)據(jù)。但是這個(gè)范圍查找的方法也太笨重了目养，沒(méi)有一點(diǎn)效率而言俩由。
所以毒嫡，使用哈希算法實(shí)現(xiàn)的索引雖然可以做到快速檢索數(shù)據(jù)癌蚁，但是沒(méi)辦法做數(shù)據(jù)高效范圍查找刽严，因此哈希索引是不適合作為 Mysql 的底層索引的數(shù)據(jù)結(jié)構(gòu)咸这。

• 二叉查找樹(shù)（BST:Binary Search True）
  二叉查找樹(shù)是一種支持?jǐn)?shù)據(jù)快速查找的數(shù)據(jù)結(jié)構(gòu)瘪吏，如圖下所示:

  
  
  image.png
  
  

  二叉查找樹(shù)的時(shí)間復(fù)雜度是 O(lgn)吁讨，比如針對(duì)上面這個(gè)二叉樹(shù)結(jié)構(gòu)痊项，我們需要計(jì)算比較 3 次就可以檢索到 id=7 的數(shù)據(jù)陷谱，相對(duì)于直接遍歷查詢省了一半的時(shí)間褪子，從檢索效率上看來(lái)是能做到高速檢索的拆吆。此外二叉樹(shù)的結(jié)構(gòu)能不能解決哈希索引不能提供的范圍查找功能呢肛鹏？
  答案是可以的逸邦。觀察上面的圖，二叉樹(shù)的葉子節(jié)點(diǎn)都是按序排列的在扰，從左到右依次升序排列缕减，如果我們需要找 id>5 的數(shù)據(jù)，那我們?nèi)〕龉?jié)點(diǎn)為 6 的節(jié)點(diǎn)以及其右子樹(shù)就可以了芒珠，范圍查找也算是比較容易實(shí)現(xiàn)桥狡。
  但是普通的二叉查找樹(shù)有個(gè)致命缺點(diǎn)：極端情況下會(huì)退化為線性鏈表，二分查找也會(huì)退化為遍歷查找，時(shí)間復(fù)雜退化為 O（N）裹芝，檢索性能急劇下降部逮。比如以下這個(gè)情況，二叉樹(shù)已經(jīng)極度不平衡了嫂易，已經(jīng)退化為鏈表了兄朋，檢索速度大大降低。此時(shí)檢索 id=7 的數(shù)據(jù)的所需要計(jì)算的次數(shù)已經(jīng)變?yōu)?7 了怜械。

  
  
  image.png

在數(shù)據(jù)庫(kù)中蜈漓，數(shù)據(jù)的自增是一個(gè)很常見(jiàn)的形式，比如一個(gè)表的主鍵是 id宫盔，而主鍵一般默認(rèn)都是自增的融虽，如果采取二叉樹(shù)這種數(shù)據(jù)結(jié)構(gòu)作為索引，那上面介紹到的不平衡狀態(tài)導(dǎo)致的線性查找的問(wèn)題必然出現(xiàn)灼芭。因此有额，簡(jiǎn)單的二叉查找樹(shù)存在不平衡導(dǎo)致的檢索性能降低的問(wèn)題，是不能直接用于實(shí)現(xiàn) Mysql 底層索引的彼绷。

• AVL樹(shù)和紅黑樹(shù)(自調(diào)整平衡)
  二叉查找樹(shù)存在不平衡問(wèn)題巍佑，因此學(xué)者提出通過(guò)樹(shù)節(jié)點(diǎn)的自動(dòng)旋轉(zhuǎn)和調(diào)整，讓二叉樹(shù)始終保持基本平衡的狀態(tài)寄悯，就能保持二叉查找樹(shù)的最佳查找性能了萤衰。基于這種思路的自調(diào)整平衡狀態(tài)的二叉樹(shù)有 AVL 樹(shù)和紅黑樹(shù)猜旬。
  首先簡(jiǎn)單介紹紅黑樹(shù)脆栋，這是一顆會(huì)自動(dòng)調(diào)整樹(shù)形態(tài)的樹(shù)結(jié)構(gòu)，比如當(dāng)二叉樹(shù)處于一個(gè)不平衡狀態(tài)時(shí)洒擦，紅黑樹(shù)就會(huì)自動(dòng)左旋右旋節(jié)點(diǎn)以及節(jié)點(diǎn)變色椿争，調(diào)整樹(shù)的形態(tài)，使其保持基本的平衡狀態(tài)（時(shí)間復(fù)雜度為 O（logn））熟嫩，也就保證了查找效率不會(huì)明顯減低秦踪。比如從 1 到 7 升序插入數(shù)據(jù)節(jié)點(diǎn)，如果是普通的二叉查找樹(shù)則會(huì)退化成鏈表掸茅，但是紅黑樹(shù)則會(huì)不斷調(diào)整樹(shù)的形態(tài)椅邓，使其保持基本平衡狀態(tài)，如下圖所示昧狮。下面這個(gè)紅黑樹(shù)下查找 id=7 的所要比較的節(jié)點(diǎn)數(shù)為 4景馁，依然保持二叉樹(shù)不錯(cuò)的查找效率。
  紅黑樹(shù)擁有不錯(cuò)的平均查找效率陵且，也不存在極端的 O(n)情況裁僧，那紅黑樹(shù)作為 Mysql 底層索引實(shí)現(xiàn)是否可以呢个束？其實(shí)紅黑樹(shù)也存在一些問(wèn)題，觀察下面這個(gè)例子聊疲。
  紅黑樹(shù)順序插入 1~7 個(gè)節(jié)點(diǎn)茬底，查找 id=7 時(shí)需要計(jì)算的節(jié)點(diǎn)數(shù)為 4。

image.png

紅黑樹(shù)順序插入 1~16 個(gè)節(jié)點(diǎn)获洲，查找 id=16 需要比較的節(jié)點(diǎn)數(shù)為 6 次阱表。觀察一下這個(gè)樹(shù)的形態(tài)，是不是當(dāng)數(shù)據(jù)是順序插入時(shí)贡珊，樹(shù)的形態(tài)一直處于“右傾”的趨勢(shì)呢最爬？從根本上上看，紅黑樹(shù)并沒(méi)有完全解決二叉查找樹(shù)雖然這個(gè)“右傾”趨勢(shì)遠(yuǎn)沒(méi)有二叉查找樹(shù)退化為線性鏈表那么夸張门岔，但是數(shù)據(jù)庫(kù)中的基本主鍵自增操作爱致，主鍵一般都是數(shù)百萬(wàn)數(shù)千萬(wàn)的，如果紅黑樹(shù)存在這種問(wèn)題寒随，對(duì)于查找性能而言也是巨大的消耗糠悯，我們數(shù)據(jù)庫(kù)不可能忍受這種無(wú)意義的等待的。

image.png

現(xiàn)在考慮另一種更為嚴(yán)格的自平衡二叉樹(shù) AVL 樹(shù)妻往。因?yàn)?AVL 樹(shù)是個(gè)絕對(duì)平衡的二叉樹(shù)互艾，因此他在調(diào)整二叉樹(shù)的形態(tài)上消耗的性能會(huì)更多。
AVL 樹(shù)順序插入 1~7 個(gè)節(jié)點(diǎn)讯泣，查找 id=7 所要比較節(jié)點(diǎn)的次數(shù)為 3纫普。

image.png

AVL 樹(shù)順序插入 1~16 個(gè)節(jié)點(diǎn)，查找 id=16 需要比較的節(jié)點(diǎn)數(shù)為 4好渠。從查找效率而言昨稼，AVL 樹(shù)查找的速度要高于紅黑樹(shù)的查找效率（AVL 樹(shù)是 4 次比較，紅黑樹(shù)是 6 次比較）晦墙。從樹(shù)的形態(tài)看來(lái)悦昵，AVL 樹(shù)不存在紅黑樹(shù)的“右傾”問(wèn)題。也就是說(shuō)晌畅，大量的順序插入不會(huì)導(dǎo)致查詢性能的降低，這從根本上解決了紅黑樹(shù)的問(wèn)題寡痰。

image.png

總結(jié)一下 AVL 樹(shù)的優(yōu)點(diǎn)：
1.不錯(cuò)的查找性能（O（logn））抗楔，不存在極端的低效查找的情況。
2.可以實(shí)現(xiàn)范圍查找拦坠、數(shù)據(jù)排序连躏。
看起來(lái) AVL 樹(shù)作為數(shù)據(jù)查找的數(shù)據(jù)結(jié)構(gòu)確實(shí)很不錯(cuò)，但是 AVL 樹(shù)并不適合做 Mysql 數(shù)據(jù)庫(kù)的索引數(shù)據(jù)結(jié)構(gòu)贞滨，因?yàn)榭紤]一下這個(gè)問(wèn)題：
數(shù)據(jù)庫(kù)查詢數(shù)據(jù)的瓶頸在于磁盤(pán) IO入热，如果使用的是 AVL 樹(shù)拍棕，我們每一個(gè)樹(shù)節(jié)點(diǎn)只存儲(chǔ)了一個(gè)數(shù)據(jù)，我們一次磁盤(pán) IO 只能取出來(lái)一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)加載到內(nèi)存里勺良，那比如查詢 id=7 這個(gè)數(shù)據(jù)我們就要進(jìn)行磁盤(pán) IO 三次绰播，這是多么消耗時(shí)間的。所以我們?cè)O(shè)計(jì)數(shù)據(jù)庫(kù)索引時(shí)需要首先考慮怎么盡可能減少磁盤(pán) IO 的次數(shù)尚困。
磁盤(pán) IO 有個(gè)有個(gè)特點(diǎn)蠢箩，就是從磁盤(pán)讀取 1B 數(shù)據(jù)和 1KB 數(shù)據(jù)所消耗的時(shí)間是基本一樣的，我們就可以根據(jù)這個(gè)思路事甜，我們可以在一個(gè)樹(shù)節(jié)點(diǎn)上盡可能多地存儲(chǔ)數(shù)據(jù)谬泌，一次磁盤(pán) IO 就多加載點(diǎn)數(shù)據(jù)到內(nèi)存，這就是 B 樹(shù)逻谦，B+樹(shù)的的設(shè)計(jì)原理了掌实。

• B樹(shù)
  下面這個(gè) B 樹(shù)，每個(gè)節(jié)點(diǎn)限制最多存儲(chǔ)兩個(gè) key邦马，一個(gè)節(jié)點(diǎn)如果超過(guò)兩個(gè) key 就會(huì)自動(dòng)分裂潮峦。比如下面這個(gè)存儲(chǔ)了 7 個(gè)數(shù)據(jù) B 樹(shù)，只需要查詢兩個(gè)節(jié)點(diǎn)就可以知道 id=7 這數(shù)據(jù)的具體位置勇婴，也就是兩次磁盤(pán) IO 就可以查詢到指定數(shù)據(jù)忱嘹，優(yōu)于 AVL 樹(shù)。

  
  
  image.png
  
  

  下面是一個(gè)存儲(chǔ)了 16 個(gè)數(shù)據(jù)的 B 樹(shù)耕渴，同樣每個(gè)節(jié)點(diǎn)最多存儲(chǔ) 2 個(gè) key拘悦，查詢 id=16 這個(gè)數(shù)據(jù)需要查詢比較 4 個(gè)節(jié)點(diǎn)，也就是經(jīng)過(guò) 4 次磁盤(pán) IO橱脸〈∶祝看起來(lái)查詢性能與 AVL 樹(shù)一樣。

  
  
  
  但是考慮到磁盤(pán) IO 讀一個(gè)數(shù)據(jù)和讀 100 個(gè)數(shù)據(jù)消耗的時(shí)間基本一致添诉，那我們的優(yōu)化思路就可以改為：盡可能在一次磁盤(pán) IO 中多讀一點(diǎn)數(shù)據(jù)到內(nèi)存屁桑。這個(gè)直接反映到樹(shù)的結(jié)構(gòu)就是，每個(gè)節(jié)點(diǎn)能存儲(chǔ)的 key 可以適當(dāng)增加栏赴。
  當(dāng)我們把單個(gè)節(jié)點(diǎn)限制的 key 個(gè)數(shù)設(shè)置為 6 之后蘑斧，一個(gè)存儲(chǔ)了 7 個(gè)數(shù)據(jù)的 B 樹(shù)，查詢 id=7 這個(gè)數(shù)據(jù)所要進(jìn)行的磁盤(pán) IO 為 2 次须眷。
  
  image.png
  
  

  一個(gè)存儲(chǔ)了 16 個(gè)數(shù)據(jù)的 B 樹(shù)竖瘾，查詢 id=7 這個(gè)數(shù)據(jù)所要進(jìn)行的磁盤(pán) IO 為 2 次。相對(duì)于 AVL 樹(shù)而言磁盤(pán) IO 次數(shù)降低為一半花颗。

  
  
  image.png
  
  所以數(shù)據(jù)庫(kù)索引數(shù)據(jù)結(jié)構(gòu)的選型而言捕传，B 樹(shù)是一個(gè)很不錯(cuò)的選擇±┤埃總結(jié)來(lái)說(shuō)庸论，B 樹(shù)用作數(shù)據(jù)庫(kù)索引有以下優(yōu)點(diǎn)：
  1.優(yōu)秀檢索速度职辅，時(shí)間復(fù)雜度：B 樹(shù)的查找性能等于 O（h*logn），其中 h 為樹(shù)高聂示，n 為每個(gè)節(jié)點(diǎn)關(guān)鍵詞的個(gè)數(shù)域携；
  2.盡可能少的磁盤(pán) IO，加快了檢索速度催什；
  3.可以支持范圍查找涵亏。

• B+樹(shù)
  B 樹(shù)和 B+樹(shù)有什么不同呢？
  第一蒲凶，B 樹(shù)一個(gè)節(jié)點(diǎn)里存的是數(shù)據(jù)气筋，而 B+樹(shù)存儲(chǔ)的是索引（地址），所以 B 樹(shù)里一個(gè)節(jié)點(diǎn)存不了很多個(gè)數(shù)據(jù)旋圆，但是 B+樹(shù)一個(gè)節(jié)點(diǎn)能存很多索引宠默，B+樹(shù)葉子節(jié)點(diǎn)存所有的數(shù)據(jù)。
  第二灵巧，B+樹(shù)的葉子節(jié)點(diǎn)是數(shù)據(jù)階段用了一個(gè)鏈表串聯(lián)起來(lái)搀矫，便于范圍查找。
  

  image.png
  
  通過(guò) B 樹(shù)和 B+樹(shù)的對(duì)比我們看出刻肄，B+樹(shù)節(jié)點(diǎn)存儲(chǔ)的是索引瓤球，在單個(gè)節(jié)點(diǎn)存儲(chǔ)容量有限的情況下，單節(jié)點(diǎn)也能存儲(chǔ)大量索引敏弃，使得整個(gè) B+樹(shù)高度降低卦羡，減少了磁盤(pán) IO。其次麦到，B+樹(shù)的葉子節(jié)點(diǎn)是真正數(shù)據(jù)存儲(chǔ)的地方绿饵，葉子節(jié)點(diǎn)用了鏈表連接起來(lái)，這個(gè)鏈表本身就是有序的瓶颠，在數(shù)據(jù)范圍查找時(shí)拟赊，更具備效率。因此 Mysql 的索引用的就是 B+樹(shù)粹淋，B+樹(shù)在查找效率吸祟、范圍查找中都有著非常不錯(cuò)的性能。
  參考文檔：
  https://mp.weixin.qq.com/s/qHJiTjpvDikFcdl9SRL97Q