前言
昨天解阅，有個(gè)女孩子問(wèn)我提高數(shù)據(jù)庫(kù)查詢性能有什么立竿見影的好方法？
這簡(jiǎn)直是一道送分題务嫡，我自豪且略帶鄙夷的說(shuō)甲抖，當(dāng)然是加「索引」了。
她又不緊不慢的問(wèn)心铃，索引為什么就能提高查詢性能准谚。
這還用問(wèn)，索引就像一本書的目錄去扣，用目錄查當(dāng)然很快柱衔。
她失望地?fù)u了搖頭，你說(shuō)的只是一個(gè)類比愉棱，可為什么通過(guò)目錄就能提高查詢速度呢唆铐。
唉，對(duì)啊奔滑，通過(guò)書目可以快速查詢艾岂，這只是一個(gè)現(xiàn)象，真正原因到底是什么呢朋其。
那女孩看著詫異且表情僵硬的我王浴，滿意而又意味深長(zhǎng)的笑笑：原來(lái)你這個(gè)男程序員也不會(huì)，看來(lái)我還得靠自己研究了梅猿。
哎氓辣，熬夜又要憔悴了我這該死的美貌。
來(lái)自同行的羞辱粒没，是可忍孰不可忍筛婉？！
于是癞松，我踏上了數(shù)據(jù)庫(kù)索引學(xué)習(xí)的不歸路爽撒，原來(lái)數(shù)據(jù)庫(kù)索引使用了一種叫 B+ 樹的古老數(shù)據(jù)結(jié)構(gòu)，當(dāng)然也有 Hash 等類型响蓉，暫且不說(shuō)硕勿，可 B+ 樹 這是個(gè)什么妖魔鬼怪呢？
下面就來(lái)淺嘗輒止的扒一扒樹的前世今生枫甲。
正文
二叉樹
由 n（ n > 0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合源武，看起來(lái)就像一個(gè)倒掛的樹，因此稱這樣的數(shù)據(jù)結(jié)構(gòu)為樹想幻。
一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)叫做度粱栖，通俗的講就是樹叉的個(gè)數(shù)。樹中最大的度叫做樹的度脏毯，也叫做階闹究。一個(gè) 2 階樹最多有 2 個(gè)子節(jié)點(diǎn)即最多有 2 叉，因此這樣的樹稱為二叉樹食店，二叉樹是樹家族中最簡(jiǎn)單的樹渣淤。
兩個(gè)叉的樹就是二叉樹赏寇，可這除了用來(lái)按一定結(jié)構(gòu)存放數(shù)據(jù)外，跟查詢性能好像也沒(méi)關(guān)系价认，不會(huì)又是一個(gè)沒(méi)用的噱頭吧嗅定。
二分查找
聽說(shuō)二叉樹的原始威力來(lái)源于一種叫做二分查找的算法。
相傳在鸚鵡的原始社會(huì)用踩，存在著森嚴(yán)的等級(jí)制度渠退，每只鳥必須按高矮順序分出等級(jí)和尊卑。
那么問(wèn)題來(lái)了捶箱，如下圖智什，怎樣才能找出最高动漾、最矮丁屎、中等高的那些鸚鵡呢、以及指定高度的那只呢?
第一種方法: 掃描法
一個(gè)一個(gè)依次測(cè)量旱眯，完畢后所有的問(wèn)題都迎刃而解晨川。
這種一個(gè)一個(gè)依次全部測(cè)量的方法叫做掃描，他的缺點(diǎn)很明顯删豺，最高和最矮共虑，需要全部測(cè)量完畢才能知曉。
而對(duì)于指定高度呀页，最好的情況是第一次就找到妈拌；最壞的情況是最后一次才找到，時(shí)間復(fù)雜度為 n蓬蝶，也就是說(shuō)從 13 個(gè)鸚鵡中找到指定身高的那只尘分，最壞的情況是查 13 次。
第二種方法：二分法
13 個(gè)鸚鵡全部聽令丸氛，按從矮到高列隊(duì)培愁，向左看齊，報(bào)數(shù)缓窜。
報(bào)數(shù)字 1 的就是最矮的定续，報(bào)數(shù)字 13 的就是最高的，報(bào)數(shù)字 7 的就是中等身高的那只禾锤。
最好和最壞的情況都是一次找到私股。而查詢性能一下子提高 13 倍，我的個(gè)乖乖恩掷，無(wú)論多個(gè)只鸚鵡倡鲸，時(shí)間復(fù)雜度都是 1，好可怕螃成。
問(wèn)題：我不服旦签，你這是偷換概念查坪，有本事對(duì)比一個(gè)查找指定高度鸚鵡的性能。
因?yàn)辂W鵡們已經(jīng)按高矮排好了隊(duì)宁炫，所以指定高度的鸚鵡偿曙，要么是站中間那個(gè)只，要么就是在它的左邊或右邊的那群里羔巢。
如果是中間那個(gè)望忆，一次就找到，如果不是只需要從中間左邊或右邊那一半中找竿秆，再在這一半中找中間那只启摄，對(duì)比身高。
以此類推幽钢，每次都把查詢的范圍減半歉备，時(shí)間復(fù)雜度log2(n)。
那么 log2(13) 就是 4匪燕，最壞的情況也才 4 次蕾羊，時(shí)間復(fù)雜度確實(shí)不是 1 了，但好像也不糟帽驯，簡(jiǎn)化如下：
問(wèn)題：如果按高矮排隊(duì)龟再，仍然需要一個(gè)一個(gè)比較，跟掃描有什么區(qū)別尼变，那還不如直接掃描呢利凑？
事實(shí)確實(shí)如此,單純的一次查詢，先排序嫌术，再二分查找哀澈，不見得比掃描快，甚至還不如蛉威。
但是日丹，在數(shù)據(jù)的世界，大部分?jǐn)?shù)據(jù)一生會(huì)被查詢無(wú)數(shù)次蚯嫌，如果只在數(shù)據(jù)降生的時(shí)候排一次序哲虾，往后余生，是不是就可以直接用二分查找择示，這似乎就是傳說(shuō)的讀多寫少束凑，以及對(duì)應(yīng)的復(fù)用。
優(yōu)點(diǎn)：
查找快
缺點(diǎn):
必須有序栅盲，需要提前排序
每次查找都需要不斷計(jì)算中間位置
二分查找樹
如果一組數(shù)據(jù)不會(huì)或不常變更汪诉，那么他們的位置也基本不變。可是每次查詢都需要重新計(jì)算中間位置是一種浪費(fèi)扒寄，而浪費(fèi)可恥鱼鼓。
我們能不能把所有中間節(jié)點(diǎn)組織起來(lái)，每次使用時(shí)该编，直接取中間節(jié)點(diǎn)?
請(qǐng)看下圖迄本，找到所有單次二分查找的中間節(jié)點(diǎn)，把他們連起來(lái)课竣，并用手提起最中間的那個(gè)節(jié)點(diǎn)嘉赎，就是一棵二分查找樹。
優(yōu)點(diǎn)：二分查找樹就是通過(guò)數(shù)據(jù)結(jié)構(gòu)的方式實(shí)現(xiàn)了二分查找算法于樟，通過(guò)存儲(chǔ)中間節(jié)點(diǎn)的數(shù)據(jù)公条，彌補(bǔ)了二分查找每次都要計(jì)算中間位置的缺點(diǎn)。
平衡二叉樹:
如果二分查找樹不斷進(jìn)行修改迂曲，比如刪除某些節(jié)點(diǎn)靶橱，經(jīng)過(guò)一段時(shí)間后，最早那個(gè)中間節(jié)點(diǎn)的數(shù)據(jù)（根）奢米，很可能就不在中間了抓韩。
中間位置就像一個(gè)天平的支點(diǎn)纠永，如果他不在中間了鬓长，那么整個(gè)天平就會(huì)失衡，失衡的世界就會(huì)坍塌成不倫不類的瘸樹尝江，甚至是降維成一個(gè)鏈表或者數(shù)組涉波。
二分查找算法的關(guān)鍵在于有序和中間節(jié)點(diǎn)，而二分查找樹的關(guān)鍵是中間節(jié)點(diǎn)的維護(hù)炭序，如果維護(hù)的節(jié)點(diǎn)已經(jīng)不在中間了啤覆，那么它就失去了意義。
所以必須保證「二分查找樹」是一個(gè)正確的樹惭聂，一個(gè)根節(jié)點(diǎn)在中心的樹窗声，一個(gè)左右子樹層級(jí)（高度）基本相等（高度相差不超過(guò)1）的樹，一個(gè)平衡的樹辜纲。
平衡二叉樹中最常見的就是紅黑樹：
紅黑樹規(guī)定了一系列節(jié)點(diǎn)顏色規(guī)則笨觅，以及對(duì)應(yīng)的左旋和右旋操作來(lái)保證顏色規(guī)則，從而達(dá)到樹的平衡性耕腾。
看到這花里胡哨的顏色以及復(fù)雜的規(guī)則见剩，讓人第一眼就望而卻步，但所有的這些扫俺，也不過(guò)是為了保證二叉樹的平衡性苍苞，由于維持平衡的操作太過(guò)麻煩，無(wú)法用一句話簡(jiǎn)單概括狼纬，只好用一堆人鬼難分的規(guī)則和步驟來(lái)實(shí)現(xiàn)羹呵，只要按著這些步驟就一定能實(shí)現(xiàn)二叉樹的平衡骂际。
平衡二叉樹 = 二分查找樹 + 平衡（左右高度相差不超過(guò) 1 ）
平衡二叉樹并未提高二分查找樹的性能，它只是保證樹不會(huì)被二向箔（多次增刪改）打擊降維成鏈表或不對(duì)稱的殘缺樹冈欢，永遠(yuǎn)維持平衡方援。
另外，不僅僅是二叉樹涛癌，其他種類的樹犯戏，也是需要有序和平衡，才能發(fā)揮最大的威力拳话。
多叉樹之 B-tree
兩個(gè)叉的樹就能折半查詢先匪，理論可以提高一倍性能，那么多個(gè)叉是不是能提高更多倍性能弃衍？
如下圖的 3 階（叉）樹（所有數(shù)據(jù)僅用于演示呀非，非真實(shí)分布）
每個(gè)節(jié)點(diǎn)維護(hù)兩個(gè)數(shù)據(jù)，并指向最多 3 個(gè)子節(jié)點(diǎn)镜盯。如圖 3 個(gè)子節(jié)點(diǎn)的數(shù)據(jù)分別為：小于 17岸裙， 17 ~ 35 ，大于 35速缆。
假設(shè)降允，從上圖中查找 10 這個(gè)數(shù)，步驟如下：
找到根節(jié)點(diǎn)艺糜，對(duì)比 10 與 17 和 35 的大小剧董，發(fā)現(xiàn) 10 < 17 在左子節(jié)點(diǎn)，也就是第 2 層節(jié)點(diǎn)破停；
從根節(jié)點(diǎn)的指針翅楼，找到左子節(jié)點(diǎn)，對(duì)比 10 與 8 和 12 的大小真慢，發(fā)現(xiàn) 8 < 10 < 12毅臊，數(shù)據(jù)在當(dāng)前節(jié)點(diǎn)的中間子節(jié)點(diǎn)，也就是第 3 層節(jié)點(diǎn)黑界；
通過(guò)上步節(jié)點(diǎn)的指針管嬉，找到中間子節(jié)點(diǎn)（第 3 層節(jié)點(diǎn)），對(duì)比 10 與 9 和 10 的大小园爷，發(fā)現(xiàn) 9 < 10 == 10宠蚂，因此找到當(dāng)前節(jié)點(diǎn)的第二數(shù)即為結(jié)果。
加上忽略的 12 個(gè)數(shù)據(jù)童社，從 26 個(gè)數(shù)據(jù)中查找一個(gè)數(shù)字 10求厕，僅僅用了 log3(26)≈ 3 次，而如果用平衡二叉樹,則需要 log2(26)≈5 次，事實(shí)證明呀癣，多叉樹確實(shí)可以再次提高查找性能美浦。
多叉樹是在二分查找樹的基礎(chǔ)上，增加單個(gè)節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)數(shù)量项栏，同時(shí)增加了樹的子節(jié)點(diǎn)數(shù)浦辨，一次計(jì)算可以把查找范圍縮小更多。
優(yōu)點(diǎn)：二叉平衡樹的基礎(chǔ)上沼沈，使加載一次節(jié)點(diǎn)流酬，可以加載更多路徑數(shù)據(jù)，同時(shí)把查詢范圍縮減到更小列另。
復(fù)雜節(jié)點(diǎn):
至此芽腾，我們列舉的數(shù)據(jù)都是孤零零的單個(gè)數(shù)字。試想页衙，你手里已經(jīng)有一個(gè)數(shù)據(jù) 10摊滔，為什么還要費(fèi)力吧唧的再?gòu)囊欢褦?shù)據(jù)中找到這個(gè) 10，自己找自己店乐？這不是有病嗎艰躺？
單個(gè)數(shù)字只能活在演示中，現(xiàn)實(shí)的世界要復(fù)雜的多眨八，我們來(lái)看一個(gè)接近真實(shí)場(chǎng)景的案例腺兴。
現(xiàn)有一個(gè)以年齡為索引的 3 階樹，存儲(chǔ)了一批用戶信息踪古，如下圖：
數(shù)字為用戶的年齡含长，其它為與樹排序查找無(wú)關(guān)的業(yè)務(wù)數(shù)據(jù)，像這種索引數(shù)據(jù)與樹排序查找無(wú)關(guān)的業(yè)務(wù)一起維護(hù)在節(jié)點(diǎn)的平衡多叉（階）樹稱為 B- 樹（ B 樹）伏穆。
缺點(diǎn)：業(yè)務(wù)數(shù)據(jù)的大小可能遠(yuǎn)遠(yuǎn)超過(guò)了索引數(shù)據(jù)的大小，每次為了查找對(duì)比計(jì)算纷纫，需要把數(shù)據(jù)加載到內(nèi)存以及 CPU 高速緩存中時(shí)枕扫，都要把索引數(shù)據(jù)和無(wú)關(guān)的業(yè)務(wù)數(shù)據(jù)全部查出來(lái)。本來(lái)一次就可以把所有索引數(shù)據(jù)加載進(jìn)來(lái)辱魁，現(xiàn)在卻要多次才能加載完烟瞧。如果所對(duì)比的節(jié)點(diǎn)不是所查的數(shù)據(jù)，那么這些加載進(jìn)內(nèi)存的業(yè)務(wù)數(shù)據(jù)就毫無(wú)用處染簇，全部拋棄参滴。
磁盤I/O
計(jì)算機(jī)的功能主要為：計(jì)算、存儲(chǔ)和網(wǎng)絡(luò)锻弓。而用于計(jì)算的數(shù)據(jù)以及計(jì)算后的結(jié)果很大一部分都需要存儲(chǔ)起來(lái)砾赔，以備后續(xù)再次使用。向磁盤中存儲(chǔ)和讀取的過(guò)程叫磁盤 I/O。磁盤的讀取方式和速度會(huì)嚴(yán)重影響到整個(gè)業(yè)務(wù)的計(jì)算性能暴心。
下面我們簡(jiǎn)單了解一下磁盤是如何工作的妓盲。
磁盤大概長(zhǎng)這個(gè)樣子：
磁盤主要由磁盤盤片、傳動(dòng)手臂专普、讀寫磁頭和馬達(dá)組成悯衬。
為了存儲(chǔ)容量,主軸像穿糖葫蘆一樣把多個(gè)磁盤片組成一個(gè)陣列。通過(guò)馬達(dá)驅(qū)動(dòng)主軸轉(zhuǎn)動(dòng)以及傳動(dòng)手臂移動(dòng)檀夹，使讀寫磁頭在磁盤片上讀寫數(shù)據(jù)筋粗。大概如下：
磁盤片由很多半徑不等的同心圓組成，這些圓被稱為磁道炸渡，數(shù)據(jù)就是寫在這些磁道上亏狰。
每個(gè)磁道又劃分成塊稱為扇區(qū)。
如果磁盤是一記事本偶摔，那么一張磁盤片就是本子的一頁(yè)紙暇唾，而主軸就是本子的裝訂線；磁道就是紙頁(yè)的行辰斋，而扇區(qū)可以看作是很寬的列策州。
如果在磁盤中存儲(chǔ)一首詩(shī),想象中大概這個(gè)樣子。
磁盤的讀 I/O 操作,需要找到數(shù)據(jù)所在的磁盤片宫仗，以及對(duì)應(yīng)的磁道和扇區(qū)够挂。這些操作類似于從一本書中找到數(shù)據(jù)所在的頁(yè)，行藕夫，列孽糖。
因?yàn)槊總€(gè)磁盤片都對(duì)應(yīng)一個(gè)磁頭，所以性能的關(guān)鍵就在于找行和列毅贮，即尋道和磁盤旋轉(zhuǎn)办悟。尋道即通過(guò)磁頭找到數(shù)據(jù)所在的磁道，相當(dāng)于換行到數(shù)據(jù)所在行滩褥。由于磁頭只能水平移動(dòng)病蛉，即只能換行尋道，無(wú)法在指定磁道上移動(dòng)瑰煎，因此需要磁盤高速旋轉(zhuǎn)移動(dòng)到指定扇區(qū)铺然，類似寫春聯(lián)時(shí)，筆不動(dòng)酒甸，紙動(dòng)魄健。
綜上所述，磁盤的讀寫是通過(guò)機(jī)械運(yùn)動(dòng)來(lái)定位數(shù)據(jù)所在位置插勤，而 cpu 是通過(guò)電信號(hào)進(jìn)行數(shù)字運(yùn)算沽瘦。粗略的認(rèn)為革骨，機(jī)械查詢數(shù)據(jù)，與光速處理數(shù)據(jù)的性能完全不是在一個(gè)量級(jí)其垄，總之一句話就是磁盤處理太慢太慢了苛蒲。
雖然磁盤處理數(shù)據(jù)太慢了，但是它是目前相對(duì)廉價(jià)且穩(wěn)定的存儲(chǔ)設(shè)備绿满，所以又不能舍棄不用臂外，但大致可以通過(guò)以下方法進(jìn)行優(yōu)化。
盡量減少 I/O 次數(shù)喇颁，比如可以使用緩存漏健；
每次 I/O 盡量獲取更多的數(shù)據(jù)；
每次 I/O 盡量獲取有用的數(shù)據(jù)橘霎，當(dāng)然相應(yīng)的也間接減少總 I/O 次數(shù)蔫浆；
多叉樹之 B+tree
作為數(shù)據(jù)庫(kù)的索引，無(wú)論用什么樣的數(shù)據(jù)結(jié)構(gòu)維護(hù)姐叁，這些數(shù)據(jù)最終都會(huì)存儲(chǔ)到磁盤中瓦盛。
鑒于磁盤 I/O 的性能問(wèn)題，以及每次 I/O 獲取數(shù)據(jù)量上限所限外潜，提高索引本身 I/O 的方法最好是原环，減少 I/O 次數(shù)和每次獲取有用的數(shù)據(jù)。
B-tree 已經(jīng)大大改進(jìn)了樹家族的性能处窥，它把多個(gè)數(shù)據(jù)集中存儲(chǔ)在一個(gè)節(jié)點(diǎn)中嘱吗，本身就可能減少了 I/O 次數(shù)或者尋道次數(shù)。
但是仍然有一個(gè)致命的缺陷滔驾，那就是它的索引數(shù)據(jù)與業(yè)務(wù)綁定在一塊谒麦，而業(yè)務(wù)數(shù)據(jù)的大小很有可能遠(yuǎn)遠(yuǎn)超過(guò)了索引數(shù)據(jù)，這會(huì)大大減小一次 I/O 有用數(shù)據(jù)的獲取哆致，間接的增加 I/O 次數(shù)去獲取有用的索引數(shù)據(jù)绕德。
因?yàn)闃I(yè)務(wù)數(shù)據(jù)才是我們查詢最終的目的，但是它又是在「二分」查找中途過(guò)程無(wú)用的數(shù)據(jù)沽瞭，因此迁匠，如果只把業(yè)務(wù)數(shù)據(jù)存儲(chǔ)在最終查詢到的那個(gè)節(jié)點(diǎn)是不是就可以了？
理想很豐滿驹溃，現(xiàn)實(shí)很骨瘦如柴，誰(shuí)知道哪個(gè)節(jié)點(diǎn)就是最終要查詢的節(jié)點(diǎn)呢延曙？
B+tree 橫空出世豌鹤，B+ 樹就是為了拆分索引數(shù)據(jù)與業(yè)務(wù)數(shù)據(jù)的平衡多叉樹。
B+ 樹中枝缔，非葉子節(jié)點(diǎn)只保存索引數(shù)據(jù)布疙，葉子節(jié)點(diǎn)保存索引數(shù)據(jù)與業(yè)務(wù)數(shù)據(jù)蚊惯。這樣即保證了葉子節(jié)點(diǎn)的簡(jiǎn)約干凈，數(shù)據(jù)量大大減小灵临，又保證了最終能查到對(duì)應(yīng)的業(yè)務(wù)數(shù)截型。既提高了單次 I/O 數(shù)據(jù)的有效性，又減少了 I/O 次數(shù)儒溉，還實(shí)現(xiàn)了業(yè)務(wù)宦焦。
但是，在數(shù)據(jù)中索引與數(shù)據(jù)是分離的顿涣，不像示例那樣的波闹？
如圖：我們只需要把真實(shí)的業(yè)務(wù)數(shù)據(jù)，換成數(shù)據(jù)所在地址就可以了涛碑，此時(shí)精堕，業(yè)務(wù)數(shù)據(jù)所在的地址在 B+ 樹中充當(dāng)業(yè)務(wù)數(shù)據(jù)。
總結(jié)
數(shù)據(jù)存儲(chǔ)在磁盤（ SSD 跟 CPU 性能也不在一個(gè)量級(jí)）蒲障，而磁盤處理數(shù)據(jù)很慢歹篓；
提高磁盤性能主要通過(guò)減少 I/O 次數(shù)，以及單次 I/O 有效數(shù)據(jù)量揉阎；
索引通過(guò)多階（一個(gè)節(jié)點(diǎn)保存多個(gè)數(shù)據(jù)庄撮，指向多個(gè)子節(jié)點(diǎn)）使樹的結(jié)構(gòu)更矮胖，從而減少 I/O 次數(shù)余黎；
索引通過(guò) B+ 樹重窟，把業(yè)務(wù)數(shù)據(jù)與索引數(shù)據(jù)分離，來(lái)提高單次 I/O 有效數(shù)據(jù)量惧财，從而減少 I/O 次數(shù)巡扇；
索引通過(guò)樹數(shù)據(jù)的有序和「二分查找」（多階樹可以假設(shè)為多分查找），大大縮小查詢范圍垮衷；
索引針對(duì)的是單個(gè)字段或部分字段厅翔，數(shù)據(jù)量本身比一條記錄的數(shù)據(jù)量要少的多，這樣即使通過(guò)掃描的方式查詢索引也比掃描數(shù)據(jù)庫(kù)表本身快的多搀突；
知識(shí)擴(kuò)展
樹的結(jié)構(gòu)最大的優(yōu)點(diǎn)就是查詢性能高刀闷，因此所有需要提高查詢性能的都可以考慮樹。
而現(xiàn)實(shí)中也確實(shí)有這樣的例子仰迁，比如：
HashMap 中的數(shù)據(jù)沖突時(shí)甸昏，鏈表轉(zhuǎn)化成紅黑樹；
數(shù)據(jù)庫(kù)索引使用的 B+ 樹徐许；
搜索引擎倒排索引使用的字典樹施蜜；
以上只是淺嘗輒止、點(diǎn)到為止的描述了數(shù)據(jù)庫(kù)使用 B+ 樹索引為什么能提高查詢性能原因及簡(jiǎn)單過(guò)程雌隅。
并沒(méi)有深入各種數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)翻默，也未提及其它索引類型和索引的具體存儲(chǔ)格式缸沃，目的僅僅是，為了讓大家對(duì)索引有一個(gè)感性的認(rèn)識(shí)修械。
