一蜓肆，b樹(shù)

因?yàn)槲覀円紤]磁盤(pán)IO的影響，它相對(duì)于內(nèi)存來(lái)說(shuō)是很慢的舀奶。數(shù)據(jù)庫(kù)索引是存儲(chǔ)在磁盤(pán)上的暑竟，當(dāng)數(shù)據(jù)量大時(shí)，就不能把整個(gè)索引全部加載到內(nèi)存了育勺，只能逐一加載每一個(gè)磁盤(pán)頁(yè)（對(duì)應(yīng)索引樹(shù)的節(jié)點(diǎn)）但荤。所以我們要減少I(mǎi)O次數(shù)，對(duì)于樹(shù)來(lái)說(shuō)涧至，IO次數(shù)就是樹(shù)的高度腹躁，而“矮胖”就是b樹(shù)的特征之一，它的每個(gè)節(jié)點(diǎn)最多包含m個(gè)孩子南蓬，m稱(chēng)為b樹(shù)的階纺非，m的大小取決于磁盤(pán)頁(yè)的大小。

一個(gè)M階的b樹(shù)具有如下幾個(gè)特征：

定義任意非葉子結(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)系优妙。

有關(guān)b樹(shù)的一些特性，注意與后面的b+樹(shù)區(qū)分：

關(guān)鍵字集合分布在整顆樹(shù)中憎账；

任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中套硼；

搜索有可能在非葉子結(jié)點(diǎn)結(jié)束；

其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找胞皱；

二邪意，b+樹(shù)

b+樹(shù)，是b樹(shù)的一種變體反砌，查詢(xún)性能更好雾鬼。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ù)的最大元素耸携。

b+樹(shù)相比于b樹(shù)的查詢(xún)優(yōu)勢(shì)：

b+樹(shù)的中間節(jié)點(diǎn)不保存數(shù)據(jù)棵癣，所以磁盤(pán)頁(yè)能容納更多節(jié)點(diǎn)元素，更“矮胖”夺衍；

b+樹(shù)查詢(xún)必須查找到葉子節(jié)點(diǎn)狈谊，b樹(shù)只要匹配到即可不用管元素位置，因此b+樹(shù)查找更穩(wěn)定（并不慢）沟沙；

對(duì)于范圍查找來(lái)說(shuō)河劝，b+樹(shù)只需遍歷葉子節(jié)點(diǎn)鏈表即可，b樹(shù)卻需要重復(fù)地中序遍歷矛紫，

為什么 MongoDB 索引選擇B-樹(shù)赎瞎，而 Mysql 索引選擇B+樹(shù)

來(lái)看下 wiki 百科上 MongoDB 的定義：

MongoDB (from humongous) is a cross-platform document-oriented database. Classified as a NoSQL database, MongoDB eschews the traditional table-based relational database structure in favor of JSON-like documents with dynamic schemas (MongoDB calls the format BSON)

這段話的大致意思是 MongoDB 是文檔型的數(shù)據(jù)庫(kù)，是一種 nosql颊咬，它使用類(lèi) Json 格式保存數(shù)據(jù)务甥。

文檔型數(shù)據(jù)庫(kù)和我們常見(jiàn)的關(guān)系型數(shù)據(jù)庫(kù)不同，一般使用 XML 或 Json 格式來(lái)保存數(shù)據(jù)喳篇，歸屬于聚合型數(shù)據(jù)庫(kù)敞临。

鍵值數(shù)據(jù)庫(kù)也屬于聚合型數(shù)據(jù)庫(kù)，熟悉 Redis 的同學(xué)應(yīng)該很好理解麸澜。

舉個(gè)例子：

加入我們要建立一個(gè)電子商務(wù)網(wǎng)站挺尿，類(lèi)似淘寶這種將商品銷(xiāo)售給用戶(hù)，那么必須存儲(chǔ)用戶(hù)信息炊邦、商品目錄编矾、訂單、收貨地址馁害、賬單地址洽沟、付款方式等。

看下傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)是如何存儲(chǔ)的：

?聚合型數(shù)據(jù)庫(kù)存儲(chǔ)模型：

用類(lèi)似 Json 的格式表示如下：

相對(duì)于 Mysql 關(guān)系型數(shù)據(jù)庫(kù)蜗细，MongoDB 這類(lèi) nosql 適用于數(shù)據(jù)模型簡(jiǎn)單裆操，性能要求高的場(chǎng)合怒详。

為什么 MongoDB 使用B-樹(shù)

MongoDB 是一種 nosql，也存儲(chǔ)在磁盤(pán)上踪区，被設(shè)計(jì)用在?數(shù)據(jù)模型簡(jiǎn)單昆烁，性能要求高的場(chǎng)合。性能要求高缎岗，看看B/B+樹(shù)的區(qū)別第一點(diǎn)：

B+樹(shù)內(nèi)節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)静尼，所有 data 存儲(chǔ)在葉節(jié)點(diǎn)導(dǎo)致查詢(xún)時(shí)間復(fù)雜度固定為 log n。而B(niǎo)-樹(shù)查詢(xún)時(shí)間復(fù)雜度不固定传泊，與 key 在樹(shù)中的位置有關(guān)鼠渺，最好為O(1)

盡可能少的磁盤(pán) IO 是提高性能的有效手段。MongoDB 是聚合型數(shù)據(jù)庫(kù)眷细，而?B-樹(shù)恰好 key 和 data 域聚合在一起拦盹。