文章出自于我自己的理解，
如果哪里寫的不對了，留言給我，或者發(fā)我郵箱superealboom@163.com。
寫這段是因?yàn)樵谖铱磩e的博客，資料學(xué)習(xí)的時候，發(fā)現(xiàn)了他們寫的錯。因?yàn)樵趯W(xué)習(xí)，所以也懷疑是自己理解的有問題，于是百般糾結(jié)，當(dāng)我翻到評論的時候，奧，原來大家都發(fā)現(xiàn)了這個錯。于是引以為鑒。

這篇文章我放在數(shù)據(jù)庫的分類下面，
那么就說存取數(shù)據(jù)庫中的數(shù)據(jù)的問題，
數(shù)據(jù)庫中的數(shù)據(jù)一般是放在磁盤里面，存取數(shù)據(jù)的時候就要訪問磁盤，
物理訪問過程：盤片旋轉(zhuǎn)，磁臂移動 兩個過程。盤片旋轉(zhuǎn)到指定位置之后，移動磁臂開始進(jìn)行數(shù)據(jù)的存取。

那么存取數(shù)據(jù)的時間(快慢)主要是在哪部分消耗呢？主要就是定位過程消耗的。
所以：考慮到提高存取數(shù)據(jù)的速率，實(shí)際上就是減少磁盤定位(I/O操作)的次數(shù)。

來舉個例子。來順序查找。

圖片是我自己畫的

為了提高效率，來二叉樹。
二叉樹的規(guī)范我就不說了，

圖片來源：https://www.cnblogs.com/tiancai/p/9024351.html

一共6個數(shù)，無論查找哪個數(shù)，最多也就定位3次。
嗯，既然二叉樹這么方便，那大家都用二叉樹好了。額，其實(shí)圖一那種情況，也算是二叉樹，那算是一種情況。如果無法保證提高效率的穩(wěn)定性，那這種結(jié)構(gòu)還是不好。
（在這里記錄一個知識點(diǎn)）
先序，中序，后序遍歷。說一點(diǎn)就好，這里的先中后，說的是根節(jié)點(diǎn)。

為了提升穩(wěn)定性，來平衡二叉樹。
平衡二叉樹用平衡因子差值來判斷是否平衡，并旋轉(zhuǎn)二叉樹。平衡因子：左右子樹高度差。平衡二叉樹里平衡因子不能超過1，否則旋轉(zhuǎn)。
長嘆一口氣，這樣穩(wěn)定了吧？
穩(wěn)定是穩(wěn)定，但是為了二叉樹的穩(wěn)定，犧牲了一些更重要的東西——時間。
當(dāng)新增刪除數(shù)據(jù)導(dǎo)致的旋轉(zhuǎn)二叉樹時，很耗時間的！
所有的操作的目的都是為了節(jié)省時間，提高效率。這樣操作舍本逐末了。但也不是絲毫沒有可取之處。
使用場景：新增刪除數(shù)據(jù)少，查找數(shù)據(jù)多的應(yīng)用場景可以。

在穩(wěn)定性的基礎(chǔ)上，再優(yōu)化一下，減少一下旋轉(zhuǎn)次數(shù)吧，來紅黑樹。
紅黑樹(Java中TreeMap)特性：
1、每個節(jié)點(diǎn)要么是紅色，要么是黑色。
2、根節(jié)點(diǎn)必須是黑色。
3、紅色節(jié)點(diǎn)不能連續(xù)（也即是，紅色節(jié)點(diǎn)的孩子和父親都不能是紅色）。
4、對于每個節(jié)點(diǎn)，從該點(diǎn)至null（樹尾端）的任何路徑，都含有相同個數(shù)的黑色節(jié)點(diǎn)。

圖片來源：百度圖片

紅黑樹旋轉(zhuǎn)的關(guān)鍵邏輯是：確保任何一個節(jié)點(diǎn)的左右子樹的高度差不會超過二者中較低那個的一倍。舉例：節(jié)點(diǎn)A，左子樹高度X，右子樹高度Y， X-Y<=min(X,Y);
所以當(dāng) X-Y > min(X,Y)，然后開始旋轉(zhuǎn)，紅黑樹的旋轉(zhuǎn)邏輯請看這位大神博客。https://www.cnblogs.com/CarpenterLee/p/5503882.html ，很清晰了。

紅黑樹已經(jīng)穩(wěn)成這樣了，滿足嗎？不滿足，還可以更穩(wěn)。來B樹。
學(xué)習(xí)B樹的時候我曾看到這樣的定義。
定義1

1.根結(jié)點(diǎn)至少有兩個子女。
2.每個中間節(jié)點(diǎn)都包含k-1個元素和k個孩子，其中 ceil（m/2） ≤ k ≤ m
3.每一個葉子節(jié)點(diǎn)都包含k-1個元素，其中 ceil（m/2） ≤ k ≤ m
4.所有的葉子結(jié)點(diǎn)都位于同一層。
5.每個節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)當(dāng)中k-1個元素正好是k個孩子包含的元素的值域劃分
6.每個結(jié)點(diǎn)的結(jié)構(gòu)為：（n，A0，K1，A1，K2，A2，…  ，Kn，An）
    其中，Ki(1≤i≤n)為關(guān)鍵字，且Ki<Ki+1(1≤i≤n-1)。
Ai(0≤i≤n)為指向子樹根結(jié)點(diǎn)的指針。且Ai所指子樹所有結(jié)點(diǎn)中的關(guān)鍵字均小于Ki+1。
n為結(jié)點(diǎn)中關(guān)鍵字的個數(shù)，滿足ceil(m/2)-1≤n≤m-1。
--------------------- 
作者：z_ryan 
來源：CSDN 
原文：https://blog.csdn.net/z_ryan/article/details/79685072 
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請附上博文鏈接！

定義2

定義任意非葉子結(jié)點(diǎn)最多只有M個兒子，且M>2；
根結(jié)點(diǎn)的兒子數(shù)為[2, M]；
除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]，向上取整；
非葉子結(jié)點(diǎn)的關(guān)鍵字個數(shù)=兒子數(shù)-1；
所有葉子結(jié)點(diǎn)位于同一層；
k個關(guān)鍵字把節(jié)點(diǎn)拆成k+1段，分別指向k+1個兒子，同時滿足查找樹的大小關(guān)系。
--------------------- 
原文：https://www.cnblogs.com/xueqiuqiu/articles/8779029.html

子女？元素？孩子？值域？關(guān)鍵字？兒子？
OMG，雖然最后我理解了博主們的意思，但是這也太費(fèi)勁兒了。所以按自己的理解，寫一個試試看。

前提：M階B樹
三種結(jié)點(diǎn)：根結(jié)點(diǎn)，中間結(jié)點(diǎn)，葉子結(jié)點(diǎn)
孩子：指一個結(jié)點(diǎn)下的子結(jié)點(diǎn)
關(guān)鍵字：結(jié)點(diǎn)中的值

1、根結(jié)點(diǎn)孩子數(shù)量：[2，M]
2、中間結(jié)點(diǎn)孩子數(shù)量：[ceil(M/2), M]
3、根結(jié)點(diǎn)和中間結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量：他們的孩子數(shù)量 -1

4、一個結(jié)點(diǎn)當(dāng)中：指向孩子指針和關(guān)鍵字的位置關(guān)系是：(指針1) 關(guān)鍵字A (指針2) 關(guān)鍵字B (指針3)
   每個關(guān)鍵字的值 > 左指針 指向的孩子樹里結(jié)點(diǎn)中的關(guān)鍵字
   每個關(guān)鍵字的值 < 右指針 指向的孩子樹里結(jié)點(diǎn)中的關(guān)鍵字

5、葉子結(jié)點(diǎn)位于同一層
6、結(jié)點(diǎn)中的關(guān)鍵字從小到大排列
7、結(jié)點(diǎn)中關(guān)鍵字不重復(fù)

圖片來源：百度圖片

B樹是很可以，但并不是對所有場景都友好。來B+樹。
先說說什么場景B樹不友好，范圍查詢：比如要找上圖中E->O，兩個字母之間的所有字母。那B樹的邏輯就是中序查找到E，繼續(xù)中序查找到O，然后拿出來字母。
那么B+樹對于這種場景就很簡單了。來先說一說B+樹基本的東西，說完也就知道了為什么用B+樹范圍查找比B樹簡單了。

1、根節(jié)點(diǎn)和中間結(jié)點(diǎn) 的 孩子數(shù)量 = 關(guān)鍵字?jǐn)?shù)量
2、根節(jié)點(diǎn)和中間結(jié)點(diǎn) 的 關(guān)鍵字 是 關(guān)鍵字對應(yīng)子樹中所有關(guān)鍵字的最大值，同時也存在于子樹中
3、根節(jié)點(diǎn)和中間結(jié)點(diǎn) 只做索引，不包含數(shù)據(jù)指針以及數(shù)據(jù)

4、葉子結(jié)點(diǎn)包含所有數(shù)據(jù)，并按照從小到大順序排列
5、葉子結(jié)點(diǎn)用指針連在一起

圖片來源：https://blog.csdn.net/u011240877/article/details/80490663

所以，對于范圍查詢：比如查找3-8之間的數(shù)字，B+樹的做法是直接在葉子結(jié)點(diǎn)上的有序鏈表上遍歷即可。
而且，B+樹比B樹的查找更加穩(wěn)定，因?yàn)槊看握业蕉紩饺~子結(jié)點(diǎn)。
那為什么B+樹每次都會到葉子結(jié)點(diǎn)？B樹每次到哪里？
B樹上的關(guān)鍵字代表一個索引key，和它同時存在的是key所指向的內(nèi)容在內(nèi)存中實(shí)際的存儲位置。如果遍歷到了某個關(guān)鍵字，那么就根據(jù)指針去真實(shí)數(shù)據(jù)的存儲位置。
B+樹上的 非葉子節(jié)點(diǎn) 關(guān)鍵字只代表索引key，葉子結(jié)點(diǎn)上存儲真實(shí)數(shù)據(jù) 或者 指向真實(shí)數(shù)據(jù)位置 的指針。