一：B樹概念
B樹也稱B-樹,英文名稱Balance Tree，所以它是一顆平衡樹叙淌，平衡因子為0秤掌，所有葉子節(jié)點(diǎn)位于同一層。同時(shí)是多路查找樹鹰霍。
特點(diǎn)：
每個(gè)節(jié)點(diǎn)可以有多個(gè)數(shù)據(jù)元素闻鉴；
平衡樹（平衡因子為0，所有葉子節(jié)點(diǎn)都位于同一層）衅谷；
查找樹椒拗；
所有節(jié)點(diǎn)的孩子節(jié)點(diǎn)數(shù)（不是數(shù)據(jù)元素個(gè)數(shù)）的最大值稱為B樹的階，一棵m階B樹稱為m叉樹获黔。
下面我們來看看B樹的定義。
每個(gè)節(jié)點(diǎn)都存有索引和數(shù)據(jù)在验，也就是對(duì)應(yīng)的key和value玷氏。索引是指向子節(jié)點(diǎn)的指針，數(shù)據(jù)是關(guān)鍵字腋舌；
每個(gè)節(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字（可以存有的鍵值對(duì)）盏触，即每個(gè)節(jié)點(diǎn)至多含有m棵子樹；
若根節(jié)點(diǎn)不是終端節(jié)點(diǎn)块饺，則至少有兩棵子樹赞辩，即最少可以只有1個(gè)關(guān)鍵字；
除根節(jié)點(diǎn)外的所有非葉節(jié)點(diǎn)至少有上限值（m/2）棵子樹授艰，即上限值（m/2）-1個(gè)關(guān)鍵字辨嗽；
每個(gè)節(jié)點(diǎn)中的關(guān)鍵字都按照從小到大的順序排列，每個(gè)關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它淮腾，而右子樹中的所有關(guān)鍵字都大于它糟需。
所以屉佳，根節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量范圍：1 <= k <= m-1，除根節(jié)點(diǎn)外的所有非葉節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量范圍：上限值（m/2）-1 <= k <= m-1洲押。
二：B+樹概述
B+樹其實(shí)和B樹是非常相似的武花，我們首先看看相同點(diǎn)。
根節(jié)點(diǎn)至少一個(gè)元素杈帐；
除根節(jié)點(diǎn)外的所有非葉節(jié)點(diǎn)元素范圍：上限值（m/2）-1 <= k <= m-1体箕。
不同點(diǎn)。
B+樹有兩種類型的節(jié)點(diǎn)：內(nèi)部節(jié)點(diǎn)（也稱索引節(jié)點(diǎn)）和葉子節(jié)點(diǎn)挑童。內(nèi)部節(jié)點(diǎn)就是非葉子節(jié)點(diǎn)累铅，內(nèi)部節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)索引炮沐，數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)争群；
內(nèi)部節(jié)點(diǎn)中的key都按照從小到大的順序排列，對(duì)于內(nèi)部節(jié)點(diǎn)中的一個(gè)key大年，左樹中的所有key都小于它换薄，右子樹中的key都大于等于它。葉子節(jié)點(diǎn)中的記錄也按照key的大小排列翔试；
每個(gè)葉子節(jié)點(diǎn)都存有相鄰葉子節(jié)點(diǎn)的指針轻要，葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接；
父節(jié)點(diǎn)存有右孩子的第一個(gè)元素的索引垦缅。
三：B樹冲泥、B+樹、紅黑樹總結(jié)
B+樹相對(duì)于B樹壁涎、紅黑樹有一些自己的優(yōu)勢(shì)凡恍，可以歸結(jié)為下面幾點(diǎn)。
單一節(jié)點(diǎn)存儲(chǔ)的元素更多怔球，使得查詢的IO次數(shù)更少嚼酝，所以也就使得它更適合做為數(shù)據(jù)庫(kù)MySQL的底層數(shù)據(jù)結(jié)構(gòu)了；
紅黑樹等查找樹也可以用來實(shí)現(xiàn)索引竟坛，但是文件系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)普遍采用 B+樹 作為索引結(jié)構(gòu)闽巩，這是因?yàn)槭褂?B+ 樹訪問磁盤數(shù)據(jù)有更高的性能；
相比較于紅黑樹担汤，B+樹有更低的樹高涎跨，平衡樹的樹高 O(h)=O(logdN)，其中 d 為每個(gè)節(jié)點(diǎn)的出度崭歧。紅黑樹的出度為 2隅很，而 B+ Tree 的出度一般都非常大，所以紅黑樹的樹高 h 很明顯比 B+ Tree 大非常多驾荣；
所有的查詢都要查找到葉子節(jié)點(diǎn)外构，查詢性能是穩(wěn)定的普泡，而B樹，每個(gè)節(jié)點(diǎn)都可以查找到數(shù)據(jù)审编，所以不穩(wěn)定撼班；
所有的葉子節(jié)點(diǎn)形成了一個(gè)有序鏈表，更加便于查找垒酬。因?yàn)?B+ Tree 的有序性砰嘁，所以除了用于查找，還可以用于排序和分組勘究。
