二線碼農(nóng)的糧食，原文連接
常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)
二叉樹(shù)
紅黑樹(shù)
Hash表
B-Tree（B樹(shù)）
Select * from t where t.col=5
我們?cè)趫?zhí)行一條查詢的Sql語(yǔ)句時(shí)候，在數(shù)據(jù)量比較大又不加索引的情況下，逐行查詢并進(jìn)行比對(duì)，每次需要從磁盤(pán)上查找，每行數(shù)據(jù)可能在磁盤(pán)不同的位置，數(shù)據(jù)比較靠后的話，一千萬(wàn)數(shù)據(jù)可能要比對(duì)幾百萬(wàn)，很耗費(fèi)資源。
Mysql衡量查詢效率的就是磁盤(pán)IO次數(shù)，那么Mysql中應(yīng)該采用什么樣的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)呢，以及為什么要使用那個(gè)數(shù)據(jù)結(jié)構(gòu)呢。
二叉樹(shù)
大多數(shù)人都知道，如果加上索引之后。把數(shù)據(jù)放在二叉樹(shù)里面，查詢會(huì)快很多，但是還有一種特殊的情況：
把一個(gè)遞增列的索引放入二叉樹(shù)中，列id作為等于5查詢目標(biāo)，就會(huì)從col為1開(kāi)始搜索，這樣要搜索幾次？二叉樹(shù)插入的數(shù)據(jù)如果大于本身，會(huì)放在父節(jié)點(diǎn)的右下角，小的會(huì)放在父節(jié)點(diǎn)的左下角，因此形成了這樣像鏈表一樣的結(jié)構(gòu)，其實(shí)本質(zhì)還是二叉樹(shù)。
需要從根節(jié)點(diǎn)遍歷，經(jīng)過(guò)5次的查找，每個(gè)節(jié)點(diǎn)都存儲(chǔ)在磁盤(pán)上，每查一個(gè)節(jié)點(diǎn)需要跟磁盤(pán)做一次IO交互，效率相比之前沒(méi)加索引也沒(méi)有太大提升,這顯然不是Mysql的索引結(jié)構(gòu)。
####### 紅黑樹(shù)
HasMap的數(shù)據(jù)結(jié)構(gòu)就是紅黑樹(shù)，原來(lái)是數(shù)組加鏈表，現(xiàn)在優(yōu)化到了數(shù)組加紅黑樹(shù)。
紅黑樹(shù)本質(zhì)還是二叉樹(shù)，還有一個(gè)名字又叫平衡二叉樹(shù)。當(dāng)一邊子節(jié)點(diǎn)比另一邊高太多的時(shí)候，會(huì)自動(dòng)旋轉(zhuǎn)平衡。當(dāng)數(shù)據(jù)量比較大的時(shí)候比如1000萬(wàn)，紅黑樹(shù)存儲(chǔ)的高度就可能達(dá)到幾十。如果數(shù)據(jù)量越大樹(shù)的高度就會(huì)越高。每查一個(gè)節(jié)點(diǎn)要進(jìn)行一次磁盤(pán)IO交互。樹(shù)的高的越高查找效率越低，很顯然紅黑樹(shù)也不是Mysql的數(shù)據(jù)結(jié)構(gòu)，早期版本Mysql有用到紅黑樹(shù)，現(xiàn)在版本沒(méi)有用到紅黑樹(shù)。那么能不能對(duì)紅黑樹(shù)做點(diǎn)改造。
B-Tree
樹(shù)的高的越高查找效率越低，那么將樹(shù)高縮小，比如限制在5層，把一層存放更多元素。把一個(gè)節(jié)點(diǎn)的數(shù)據(jù)在磁盤(pán)同一個(gè)區(qū)域全部查出來(lái)放到內(nèi)存，只做一次IO查找，就可以查到很多索引信息。B樹(shù)又叫平衡多叉樹(shù)。
索引值和具體data都在每個(gè)節(jié)點(diǎn)里，而節(jié)點(diǎn)的位置不固定，最好的情況查找值就在第一層。
B樹(shù)的特點(diǎn)就是每層節(jié)點(diǎn)數(shù)目非常多，層數(shù)很少，目的就是為了就少磁盤(pán)IO次數(shù)，B樹(shù)在提高了磁盤(pán)IO性能的同時(shí)并沒(méi)有解決元素遍歷的效率低下的問(wèn)題，由于節(jié)點(diǎn)內(nèi)部每個(gè) key 都帶著 data 域，每次查找到具體節(jié)點(diǎn)還要和data進(jìn)行順序比對(duì)，如果查找某個(gè)范圍內(nèi)數(shù)據(jù)，又需要重新遍歷。正是為了解決這個(gè)問(wèn)題，B+樹(shù)應(yīng)運(yùn)而生
B樹(shù)遍歷全部數(shù)據(jù)：
B+Tree
B+樹(shù)節(jié)點(diǎn)只存儲(chǔ) key 的副本，真實(shí)的 key 和 data 域都在葉子節(jié)點(diǎn)存儲(chǔ)，數(shù)據(jù)全部存儲(chǔ)在葉子節(jié)，并且每一個(gè)節(jié)點(diǎn)之間用指針串聯(lián)起來(lái)，形成鏈表，方便遍歷，可以跨區(qū)間訪問(wèn)，這優(yōu)點(diǎn)尤其突出在范圍查詢，不需要在一次從根節(jié)點(diǎn)到子節(jié)點(diǎn)遍歷。
B+樹(shù)遍歷全部數(shù)據(jù)：
數(shù)據(jù)量大的情況下哪個(gè)更快，我想你應(yīng)該知道了吧！
