上一次吊打各種樹(shù)這篇文章堂主檸檬帶大家學(xué)習(xí)一遍數(shù)據(jù)結(jié)構(gòu)中的各種樹(shù)，對(duì)數(shù)據(jù)結(jié)構(gòu)還不夠熟悉的同學(xué)，那篇文章可以作為基礎(chǔ)入門(mén)，我畫(huà)了很多圖理解起來(lái)不困難，建議回頭先學(xué)習(xí)下那篇文章，更容易理解本文要講的內(nèi)容。

文章里有提到B+樹(shù)被廣泛應(yīng)用于MySQL數(shù)據(jù)庫(kù)的索引實(shí)現(xiàn)，不過(guò)并未展開(kāi)細(xì)說(shuō)，但是呢B+樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)，常年出現(xiàn)在各種面試題中，這次就來(lái)一起學(xué)習(xí)下和B+樹(shù)相關(guān)的MySQL索引底層實(shí)現(xiàn)的內(nèi)容。

面試官：簡(jiǎn)單講講MySQL數(shù)據(jù)庫(kù)的索引實(shí)現(xiàn)，以及為什么這么實(shí)現(xiàn)？

這個(gè)面試題出現(xiàn)的頻率非常之高，從我自己和朋友們參加的大小廠面試都有被問(wèn)過(guò)這個(gè)問(wèn)題，大部分人可能看過(guò)一些網(wǎng)上的博客能說(shuō)出個(gè)一二三，如果面試官?zèng)]有細(xì)問(wèn)還真能混過(guò)去，但是對(duì)于細(xì)節(jié)沒(méi)能真正理解的非常透徹。

所以今天堂主檸檬就來(lái)寫(xiě)寫(xiě)這個(gè)話題，讓你知其然也知其所以然。寫(xiě)作目標(biāo)是無(wú)論你是否學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)，看完都能徹底搞懂這個(gè)問(wèn)題，花5分鐘來(lái)跟著學(xué)一遍看看我有沒(méi)有做到吧。

首先需要明白，數(shù)據(jù)庫(kù)索引是在存儲(chǔ)引擎層實(shí)現(xiàn)，常見(jiàn)的存儲(chǔ)引擎有 2 種。

InnoDB 存儲(chǔ)引擎：

innoDB存儲(chǔ)引擎支持事務(wù)，其設(shè)計(jì)目標(biāo)是面向在線事務(wù)處理的應(yīng)用，行鎖設(shè)計(jì)、支持外鍵，默認(rèn)度操作不會(huì)產(chǎn)生鎖，從MySLQ 5.5.7版本開(kāi)始，InnoDB存儲(chǔ)引擎作為默認(rèn)的存儲(chǔ)引擎存在于MySLQ中。

MyISAM 存儲(chǔ)引擎：

MyISAM存儲(chǔ)引擎不支持事務(wù)，表鎖設(shè)計(jì)，支持全文索引，主要面向離線事務(wù)處理的數(shù)據(jù)庫(kù)應(yīng)用，在InnoDB引擎成為默認(rèn)引擎之前，MyISAM存儲(chǔ)引擎一直霸占著默認(rèn)存儲(chǔ)引擎的位置，直到他被InnoDB取代，這是個(gè)悲傷的故事。

存儲(chǔ)引擎不同，索引實(shí)現(xiàn)方式也不盡相同，因此，我們先約定本文講的索引都是InnoDB存儲(chǔ)引擎實(shí)現(xiàn)的B+樹(shù)索引。

MySQL架構(gòu)

索引由存儲(chǔ)引擎實(shí)現(xiàn)，那存儲(chǔ)引擎到底是個(gè)什么東西呢？

從我們平常使用的的角度來(lái)看，對(duì)MySQL的直觀感受是命令行的各種指令，或是一個(gè)數(shù)據(jù)庫(kù)管理工具比如SQLyog的界面點(diǎn)擊操作，堂主檸檬在剛接觸MySQL時(shí)就是用的SQLyon圖形界面操作，就是下面這個(gè)小海豚。

數(shù)據(jù)庫(kù)大揭秘：10張圖告訴你MySQL為什么選B+樹(shù)做索引？

MySQL可能是世界上最流行的開(kāi)源數(shù)據(jù)庫(kù)引擎，但使用基于文本的工具和配置文件管理起來(lái)可能很困難。SQLyog提供了一個(gè)完整的圖形界面，即使對(duì)于初學(xué)者來(lái)說(shuō)，使用MySQL的強(qiáng)大功能也很簡(jiǎn)單，SQLyog直觀的圖形用戶界面使您可以輕松管理MySQL數(shù)據(jù)庫(kù)的各個(gè)方面。

不管是使用圖形界面還是命令行，我們接觸到的都只是客戶端，MySQL作為一個(gè)軟件系統(tǒng)的架構(gòu)，存儲(chǔ)引擎在MySQL服務(wù)端系統(tǒng)架構(gòu)的什么位置呢？

總的來(lái)說(shuō)，MySLQ系統(tǒng)架構(gòu)分為 3 層，直接上圖，看下MySQL的架構(gòu)劃分。

第一層：連接管理層。MySLQ是典型的CS模型軟件，所謂CS就是客戶端/服務(wù)端的意思，作為一個(gè)靠網(wǎng)絡(luò)連接的服務(wù)，必不可少的要有連接管理層，用于管理和維護(hù)MySQL服務(wù)端和客戶端之間的連接、鑒權(quán)等等。
第二層：這一層是MySQL的核心服務(wù)功能層，包括了查詢緩存、解析器、優(yōu)化器等所有跨存儲(chǔ)引擎的功能都在這一層實(shí)現(xiàn)，屏蔽掉存儲(chǔ)引擎間的差別，對(duì)上層也就是連接管理層提供統(tǒng)一的接口。
第三層：存儲(chǔ)引擎層就在這一層實(shí)現(xiàn)，負(fù)責(zé)MySQL中數(shù)據(jù)的存儲(chǔ)和提取，這其中有我們今天的主角InnoDB存儲(chǔ)引擎和它實(shí)現(xiàn)的B+樹(shù)索引。

如何指定存儲(chǔ)引擎類型

既然要研究innoDB的索引，那我們首先來(lái)創(chuàng)建一個(gè)使用innoDB存儲(chǔ)引擎的表。

MySQL目前支持的存儲(chǔ)引擎種類非常豐富，可以在連接MySQL客戶端，進(jìn)入到命令行模式下，輸入如下命令查看當(dāng)前版本MySQL提供的所有存儲(chǔ)引擎。

show engines;

可以看到上圖中有包含MyISAM 和 InnoDB 這兩種常見(jiàn)引擎，關(guān)于這些存儲(chǔ)引擎的詳細(xì)介紹，可以參考MySQL的官方文檔，我放上鏈接：

https://dev.mysql.com/doc/refman/8.0/en/storage-engines.html

好了，現(xiàn)在來(lái)創(chuàng)建數(shù)據(jù)表并指定innoDB存儲(chǔ)引擎。

舉個(gè)栗子：創(chuàng)建表一張大佬數(shù)據(jù)表 BigOld，表中第一個(gè)字段是大佬 id 標(biāo)識(shí)，第二個(gè)字段是大佬名字 name，并指定數(shù)據(jù)庫(kù)使用的存儲(chǔ)引擎類型ENGINE=InnoDB ，下面這條建表語(yǔ)句創(chuàng)建并指定了一個(gè)使用 InnoDB 存儲(chǔ)引擎的數(shù)據(jù)庫(kù)表。

CREATE TABLE BigOld (
    id INT,
    name CHAR (32), 
    PRIMARY KEY (id)) ENGINE=InnoDB;

當(dāng)然，如果你一開(kāi)始創(chuàng)建的表使用的不是InnoDB引擎，那也沒(méi)關(guān)系，還可以再創(chuàng)建表之后修改表的存儲(chǔ)引擎，像下面的這樣操作。

alert table BigOld engine = InnoDB

索引

好了，經(jīng)過(guò)前面的操作，終于我們有了一個(gè)innoDB的數(shù)據(jù)表，現(xiàn)在我們可以來(lái)講講innoDB存儲(chǔ)引擎的索引，索引的作用當(dāng)然是為了快速的存取MySQL數(shù)據(jù)庫(kù)的數(shù)據(jù)。

舉個(gè)栗子，如果把MySQL比作一個(gè)大型圖書(shū)館，其中的數(shù)據(jù)比作圖書(shū)館里的書(shū)。

圖書(shū)館 unsplash.com

你去圖書(shū)館找書(shū)，圖書(shū)館那么大我們不可能一頭扎進(jìn)去，一層層、一個(gè)個(gè)書(shū)架去找想要的書(shū)，這時(shí)候我們會(huì)在圖書(shū)管理系統(tǒng)中通過(guò)圖書(shū)編號(hào)（索引）查詢到圖書(shū)所在的樓層，到了指定的樓層在通過(guò)書(shū)架上的提示找到對(duì)應(yīng)區(qū)域，最終在某個(gè)書(shū)架找到想要的書(shū)，這個(gè)圖書(shū)編號(hào)就起到索引的作用，幫助我們快速找到圖書(shū)（數(shù)據(jù)）。

存儲(chǔ)形式

InnoDB存儲(chǔ)引擎用B+樹(shù)實(shí)現(xiàn)索引，說(shuō)到B+樹(shù)不得不提到他的兄弟B樹(shù)，這兩者的區(qū)別比較微妙，但查詢磁盤(pán)存儲(chǔ)數(shù)據(jù)的性能上卻相差很大，要知道為何MySQL InnoDB 選擇B+樹(shù)而不選擇B樹(shù)做索引，我們先來(lái)假設(shè)分別用這兩種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)索引對(duì)比一下。

B樹(shù)索引

拿來(lái)一本數(shù)據(jù)結(jié)構(gòu)的教材，我們翻開(kāi)B樹(shù)的定義。一棵M階的b樹(shù)是這么定義的：

定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子，且M>2；

根結(jié)點(diǎn)的兒子數(shù)為[2, M]；

除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]，向上取整；

非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=兒子數(shù)-1；

所有葉子結(jié)點(diǎn)位于同一層；

k個(gè)關(guān)鍵字把節(jié)點(diǎn)拆成k+1段，分別指向k+1個(gè)兒子，同時(shí)滿足查找樹(shù)的大小關(guān)系。

看完你大概有點(diǎn)懵，不過(guò)沒(méi)關(guān)系，我們現(xiàn)是要對(duì)比它和B+樹(shù)在數(shù)據(jù)庫(kù)索引上的使用，不是要去手寫(xiě)一個(gè)數(shù)據(jù)庫(kù)索引，只要抓住它主要的特點(diǎn)便于理解幫助我們理解索引原理即可，這里抓住B樹(shù)最主要的兩個(gè)特點(diǎn)：

非葉子節(jié)點(diǎn)只存放「索引」和指向子節(jié)點(diǎn)的「指針」。
葉子節(jié)點(diǎn)存放「索引」和「數(shù)據(jù)」，且葉子節(jié)點(diǎn)之間沒(méi)有關(guān)聯(lián)。

便于理解，假如在數(shù)據(jù)庫(kù)中使用B樹(shù)來(lái)做索引結(jié)構(gòu)，我試著畫(huà)出這個(gè)B樹(shù)的索引結(jié)構(gòu)圖，如下：

B+樹(shù)索引

看完了B樹(shù)索引實(shí)現(xiàn)，現(xiàn)在我們來(lái)用B+樹(shù)實(shí)現(xiàn)索引看看，一樣的隨便打開(kāi)一本數(shù)據(jù)結(jié)構(gòu)教材找到B+樹(shù)的定義，一顆M階的B+樹(shù)：

有n棵子樹(shù)的非葉子結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字（b樹(shù)是n-1個(gè)），這些關(guān)鍵字不保存數(shù)據(jù)，只用來(lái)索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)（b樹(shù)是每個(gè)關(guān)鍵字都保存數(shù)據(jù)）。

所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。

所有的非葉子結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含其子樹(shù)中的最大（或最小）關(guān)鍵字。

通常在b+樹(shù)上有兩個(gè)頭指針，一個(gè)指向根結(jié)點(diǎn)，一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)。

同一個(gè)數(shù)字會(huì)在不同節(jié)點(diǎn)中重復(fù)出現(xiàn)，根節(jié)點(diǎn)的最大元素就是b+樹(shù)的最大元素。

如果以前沒(méi)接觸過(guò)數(shù)據(jù)結(jié)構(gòu)相關(guān)概念，看完估計(jì)還是不大明白，沒(méi)關(guān)系，那不是本文的重點(diǎn)，我們不去深究細(xì)枝末節(jié)。

我來(lái)幫你總結(jié)下，B+樹(shù)和B樹(shù)有很多相同的特點(diǎn)，但也有一些不同讓B+樹(shù)在查詢磁盤(pán)存儲(chǔ)的數(shù)據(jù)時(shí)有更好的性能（為什么？我們稍后講），最大的不同是下面兩個(gè)：

「數(shù)據(jù)」只存放葉子節(jié)點(diǎn)上面的，非葉子節(jié)點(diǎn)存放「索引」和「指針」。
葉子節(jié)點(diǎn)按大小順序通過(guò)雙向鏈表連接起來(lái)，可以像遍歷鏈表一樣遍歷整棵B+樹(shù)。

innoDB的選擇

innoDB的索引選擇用B+樹(shù)來(lái)實(shí)現(xiàn)，B樹(shù)和B+樹(shù)非常相似，為什么用B+樹(shù)不用B樹(shù)做索引呢？這就要從數(shù)據(jù)庫(kù)的存儲(chǔ)方式說(shuō)起。

性能瓶頸

innoDB索引以B+樹(shù)形式組織存儲(chǔ)，我們首先要明白B+樹(shù)的每個(gè)節(jié)點(diǎn)不是保存在內(nèi)存而是放在屬于外部存儲(chǔ)的「磁盤(pán)頁(yè)」中。

為什么呢？因?yàn)閮?nèi)存快是快，但是它貴啊！而且很多數(shù)據(jù)不是熱點(diǎn)數(shù)據(jù)，十天半個(gè)月都用不上，完全沒(méi)必要都放在內(nèi)存里面，想想看如果淘寶會(huì)把那種萬(wàn)億級(jí)別的交易訂單數(shù)據(jù)如果都存在內(nèi)存中嗎，馬爸爸雖然有錢(qián)也不至于這么奢侈。

重點(diǎn)關(guān)注下這里所說(shuō)的磁盤(pán)頁(yè)，的大小每個(gè)系統(tǒng)可能不一樣，就堂主所用的這個(gè)centos linux系統(tǒng)來(lái)說(shuō)，通過(guò)下面的命令查看磁盤(pán)頁(yè)大小為 4096B 也就是 4KB

[lemon/test]$ getconf PAGE_SIZE
4096

這些磁盤(pán)數(shù)據(jù)頁(yè)如果是B+樹(shù)的葉子節(jié)點(diǎn)，那就保存著關(guān)鍵字和數(shù)據(jù)（就是我們用 INSERT 語(yǔ)句塞進(jìn)數(shù)據(jù)庫(kù)的那些數(shù)據(jù)）。

如果是非葉子節(jié)點(diǎn)那就保存著關(guān)鍵字和指針（指向子節(jié)點(diǎn)的指針），從上圖B+樹(shù)實(shí)現(xiàn)的索引示意圖也可以看到這兩種存儲(chǔ)形式的差別。

內(nèi)存VS外存

當(dāng)我們?cè)贛ySQL InnoDB中執(zhí)行 select 查詢語(yǔ)句，這個(gè)查找數(shù)據(jù)的過(guò)程是這樣的：

沿著B(niǎo)+樹(shù)索引來(lái)查找一個(gè)給定關(guān)鍵字（或者范圍關(guān)鍵字）的所在的數(shù)據(jù)行。
找到數(shù)據(jù)行所在的磁盤(pán)頁(yè)，把這個(gè)磁盤(pán)頁(yè)加載到內(nèi)存中。
在內(nèi)存中進(jìn)行查找（比如二分查找），最終得到目標(biāo)數(shù)據(jù)行內(nèi)容。

我們知道磁盤(pán)是外部存儲(chǔ)設(shè)備，那MySQL數(shù)據(jù)庫(kù)查找的時(shí)候?qū)⒋疟P(pán)中數(shù)據(jù)讀入內(nèi)存這個(gè)過(guò)程是非常緩慢的，對(duì)于機(jī)械硬盤(pán)具體來(lái)說(shuō)，從磁盤(pán)加載數(shù)據(jù)需要經(jīng)過(guò)尋道、旋轉(zhuǎn)以及傳輸?shù)倪@些過(guò)程，時(shí)間花費(fèi)至少是幾十毫秒，作為對(duì)比，DDR4內(nèi)存尋址時(shí)間僅為6ns左右。

機(jī)械硬盤(pán)

內(nèi)存讀取速度是磁盤(pán)讀取速度的100萬(wàn)倍！雖然現(xiàn)在固態(tài)硬盤(pán)的速度提升了很多，但和內(nèi)存比起來(lái)還是有很大的差距，所以要盡量減少數(shù)據(jù)庫(kù)對(duì)磁盤(pán)數(shù)據(jù)頁(yè)的隨機(jī)IO操作。

由于磁盤(pán)讀寫(xiě)耗時(shí)的原因，在高并發(fā)系統(tǒng)中關(guān)系型數(shù)據(jù)庫(kù)MySQL會(huì)成為系統(tǒng)性能瓶頸。

在高并發(fā)服務(wù)中幾十毫秒的的耗時(shí)太久了，假設(shè)10ms處理一個(gè)請(qǐng)求，那1秒處理100個(gè) QPS=100 對(duì)比秒殺這一類的場(chǎng)景這個(gè)吞吐量完全是不夠用的，這也是現(xiàn)在像redis這樣的高速緩存數(shù)據(jù)庫(kù)會(huì)站在前面，為MySQL擋一刀的原因，因?yàn)镽edis都是內(nèi)存操作，速度非常快！

Why B+樹(shù)？

為了更方便的說(shuō)明B樹(shù)和B+樹(shù)兩種存儲(chǔ)結(jié)構(gòu)的差異，我們來(lái)對(duì)比下兩種樹(shù)實(shí)現(xiàn)的索引上讀取數(shù)據(jù)的過(guò)程，i再來(lái)回答innoDB 引擎為什么選B+樹(shù)。

為方便對(duì)比，假設(shè)我們?cè)贐和B+樹(shù)中我們都要「查詢 1 < id < 6 之間」的所有數(shù)據(jù)行。

B樹(shù)索引

先來(lái)看下如果索引用B樹(shù)來(lái)實(shí)現(xiàn)，查找數(shù)據(jù)的流程圖：

在不考慮任何優(yōu)化的前提下，圖中綠色虛線是在B樹(shù)索引上查找數(shù)據(jù)的遍歷軌跡，來(lái)拆解一下：

從索引樹(shù)根節(jié)點(diǎn)開(kāi)始，加載磁盤(pán)頁(yè) page1 找到第一個(gè)節(jié)點(diǎn) key=1 數(shù)據(jù)行（1，小林）不符合。
繼續(xù)通過(guò)指針找到磁盤(pán)頁(yè)面page2，加載磁盤(pán)頁(yè)page2到內(nèi)存，key=2 符合，讀取數(shù)據(jù)行（2, 石頭）
重新加載磁盤(pán)頁(yè) page1 找到第二個(gè)節(jié)點(diǎn) key=3符合，讀取數(shù)據(jù)行（3，軒轅）。
繼續(xù)通過(guò)指針加載磁盤(pán)頁(yè) page4 到內(nèi)存，key=4 符合，讀取數(shù)據(jù)行（4，小北）。
重新加載磁盤(pán)頁(yè) page1 找到第三個(gè)節(jié)點(diǎn) key=5 符合，讀取數(shù)據(jù)行（5，why神）。

數(shù)一數(shù)上面的5個(gè)步驟有幾個(gè)「加載磁盤(pán)頁(yè)」字眼，5個(gè)，還記得上面我們說(shuō)的：**加載磁盤(pán)數(shù)據(jù)非常費(fèi)時(shí)！**這種隨機(jī)大量的磁盤(pán)IO造成了B樹(shù)索引的的性能瓶頸，使其與innoDB索引無(wú)緣。

B+樹(shù)索引

再來(lái)看下現(xiàn)在innoDB的用B+樹(shù)的實(shí)現(xiàn)方案吧，同樣的查詢條件，還是畫(huà)出數(shù)據(jù)查找的遍歷軌跡：

在不考慮任何優(yōu)化的前提下，圖中綠色虛線是在innoDB B+樹(shù)索引上查找數(shù)據(jù)的遍歷軌跡，同樣來(lái)拆解一下：

從索引樹(shù)根節(jié)點(diǎn)開(kāi)始，加載磁盤(pán)頁(yè) page1 找到第一個(gè)節(jié)點(diǎn) key=1不符合，繼續(xù)往下搜索。
通過(guò)指針找到磁盤(pán)頁(yè)page2, 加載磁盤(pán)頁(yè)page2 到內(nèi)存，其中存放了key=1、2的數(shù)據(jù)行，讀取符合條件數(shù)據(jù)行。
由于葉子節(jié)點(diǎn)間組成雙向鏈表，直接順著page2 加載磁盤(pán)頁(yè)page3 、加載磁盤(pán)頁(yè)page4，讀取其中符合條件的數(shù)據(jù)行。

這其中涉及了4次加載磁盤(pán)頁(yè)的操作，看起來(lái)只是比上面的B樹(shù)少了一次，但這是在我的簡(jiǎn)單例子，為了便于理解數(shù)據(jù)量比較少。

實(shí)際應(yīng)用中B+確實(shí)能夠減少大量的磁盤(pán)IO，從而大大提高查詢性能，而且由于B+樹(shù)根節(jié)點(diǎn)的數(shù)據(jù)已經(jīng)是排序好的雙向鏈表，我們可以像鏈表一樣遍歷所有數(shù)據(jù)，非常適合范圍查找和排序操作！

再談B樹(shù)

B樹(shù)索引并非一無(wú)是處。雖然我們前面詳細(xì)對(duì)比了在innoDB中使用B+樹(shù)索引的優(yōu)勢(shì)，但不要以為B樹(shù)就一無(wú)是處了，一種數(shù)據(jù)結(jié)構(gòu)被設(shè)計(jì)出來(lái)肯定是有使用場(chǎng)景的需求，不然誰(shuí)也不會(huì)閑著沒(méi)事折騰出一個(gè)東西，你說(shuō)對(duì)吧。

事實(shí)上B樹(shù)也被用于實(shí)現(xiàn)數(shù)據(jù)庫(kù)索引，只不過(guò)不是在MySQL上。在MongoDB的索引設(shè)計(jì)上就使用了B樹(shù)做索引，什么是MongoDB呢？我不做過(guò)多介紹，感興趣的可以下來(lái)了解一下，下面這段話來(lái)自MongoDB 英文Wiki

MongoDB is a cross-platform document-oriented database program. Classified as a NoSQL database program, MongoDB uses JSON-like documents with optional schemas. MongoDB is developed by MongoDB Inc. and licensed under the Server Side Public License (SSPL).

只需要知道它和MySQl不同，MongoDB是一種文檔型的非關(guān)系型數(shù)據(jù)庫(kù)，被劃分為NoSql數(shù)據(jù)庫(kù)，使用類似JSON的語(yǔ)法存儲(chǔ)文檔，熟悉Redis的同學(xué)應(yīng)該很容易理解NoSQL的含義。

因?yàn)殛P(guān)系型數(shù)據(jù)庫(kù)比如 MySQL 經(jīng)常需要執(zhí)行遍歷和范圍查找的操作，B+樹(shù)的特點(diǎn)正是迎合了這樣的需求。但是在MongoDB這樣的NoSLQ數(shù)據(jù)庫(kù)中，在數(shù)據(jù)表的設(shè)計(jì)層面就決定了不會(huì)有太多的遍歷和范圍查找，基本就是一個(gè)鍵對(duì)應(yīng)一個(gè)值的單一查詢。

在MongoDB上的查找如果用B+樹(shù)來(lái)實(shí)現(xiàn)索引的話，由于非葉子節(jié)點(diǎn)不存放數(shù)據(jù)，每次查詢必須搜索到B+樹(shù)的葉子節(jié)點(diǎn)才能獲取到數(shù)據(jù)，時(shí)間復(fù)雜度是固定的樹(shù)的高度 log n；

而如果用B樹(shù)實(shí)現(xiàn)索引，由于每個(gè)節(jié)點(diǎn)都可以存放數(shù)據(jù)，幸運(yùn)的話有可能不必找到葉子節(jié)點(diǎn)就能取得數(shù)據(jù)，復(fù)雜度更低，再來(lái)看下B樹(shù)實(shí)現(xiàn)的索引，如果換作是 MongoDB 你仔細(xì)品。

雖然沒(méi)有MySQL的使用普及程度那么高，用B樹(shù)實(shí)現(xiàn)索引的MongoDB很多大公司也都有使用。

使用客戶

脫離業(yè)務(wù)場(chǎng)景談具體實(shí)現(xiàn)都是耍流氓。正是由于關(guān)系型數(shù)據(jù)庫(kù)和非關(guān)系型數(shù)據(jù)庫(kù)應(yīng)用場(chǎng)景的不同，工程實(shí)現(xiàn)上最終會(huì)在損失和收益中找到平衡點(diǎn)，使得B樹(shù)和B+樹(shù)在不同數(shù)據(jù)庫(kù)上有各自的用武之地。

所以下次面試和面試官夸MySQL B+樹(shù)索引好處的時(shí)候，注意別把 B 樹(shù)噴的太慘，以防面試官來(lái)個(gè)回馬槍，讓你說(shuō)說(shuō)為啥MongoDB還要用B樹(shù)來(lái)實(shí)現(xiàn)索引？這時(shí)候雖然你心里笑開(kāi)了花，還是要假裝再思考下，愣著干嘛，接著繼續(xù)吹B樹(shù)啊。

感謝各位的閱讀，文章的目的是分享對(duì)知識(shí)的理解，技術(shù)類文章我都會(huì)反復(fù)求證以求最大程度保證準(zhǔn)確性，若文中出現(xiàn)明顯紕漏也歡迎指出，我們一起在探討中學(xué)習(xí)。

Hi，我是堂主檸檬，一線互聯(lián)網(wǎng)大廠后端程序員一枚，個(gè)人技術(shù)gzh主要分享后端開(kāi)發(fā)相關(guān)的技術(shù)學(xué)習(xí)，每篇文章都是我精心創(chuàng)作，如果文章對(duì)你有幫助，這次一定不要白piao，點(diǎn)贊 或分享給需要的朋友，這對(duì)檸檬很重要，在此先謝過(guò)各位大佬了！我是檸檬，我們下期再見(jiàn)。