在這里插入圖片描述
說這個(gè)面試題膀钠，先來回顧一下B+樹、B-樹裹虫、平衡二叉樹肿嘲、紅黑樹的概念
平衡二叉樹
- 平衡二叉樹又被稱為AVL樹
- 平衡二叉樹是一顆空樹或者它的左右兩個(gè)子樹的高度差的絕對值不超過1，并且左右子樹也是平衡樹
- 非葉子節(jié)點(diǎn)值大于左子節(jié)點(diǎn)值而小于右子節(jié)點(diǎn)值
- 非葉子節(jié)點(diǎn)最多擁有兩個(gè)子節(jié)點(diǎn)
在這里插入圖片描述
紅黑樹
- 每個(gè)節(jié)點(diǎn)要么是紅色要么是黑色
- 根節(jié)點(diǎn)是黑色
- 每個(gè)葉子節(jié)點(diǎn)(NIL)是黑色
- 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)一定為黑色
- 任意一個(gè)節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑都包含數(shù)量相同的黑色節(jié)點(diǎn)
- 如果一個(gè)節(jié)點(diǎn)存在黑子節(jié)點(diǎn)筑公，那么該節(jié)點(diǎn)肯定有兩個(gè)子節(jié)點(diǎn)
在這里插入圖片描述
B-樹
- 每個(gè)節(jié)點(diǎn)中雳窟，都包含數(shù)據(jù)(key和data域)和指針，相互間隔
- 葉節(jié)點(diǎn)具有相同的深度匣屡，葉節(jié)點(diǎn)的指針為空
- 節(jié)點(diǎn)中的數(shù)據(jù)索引從左到右遞增排列
- 所有索引元素不重復(fù)
b-.png
B+樹
- 非葉子節(jié)點(diǎn)中不存儲data封救，只存儲索引拇涤，可以放更多的索引
- 葉子節(jié)點(diǎn)包含所有索引字段
- 葉子節(jié)點(diǎn)包含數(shù)據(jù)(key和data域)和指針
- 葉子節(jié)點(diǎn)用指針連接，提高區(qū)間訪問的性能
在這里插入圖片描述
平衡二叉樹不足
- 考慮到極端情況下兴泥，每次插入的數(shù)據(jù)都比上一次插入的數(shù)據(jù)大工育，那么用平衡二叉樹就會以線性方式進(jìn)行存儲，時(shí)間復(fù)雜度為O(n)搓彻。數(shù)據(jù)量很大時(shí)如绸，在mysql中一張表存儲百萬條數(shù)據(jù)是很正常的一件事，這樣會導(dǎo)致樹的深度更深旭贬，mysql讀取時(shí)消耗大量io怔接。
- mysql進(jìn)行過磁盤讀取時(shí)，是以頁為單位進(jìn)行讀取稀轨，每個(gè)節(jié)點(diǎn)表示一頁扼脐。而平衡二叉樹每個(gè)節(jié)點(diǎn)存儲一個(gè)關(guān)鍵詞，導(dǎo)致存儲空間被浪費(fèi)奋刽。
B-樹相比平衡二叉樹優(yōu)點(diǎn)
- 每個(gè)節(jié)點(diǎn)存儲多個(gè)多個(gè)關(guān)鍵詞瓦侮，合理利用空間大小，每次mysql進(jìn)行讀取時(shí)佣谐，都會進(jìn)行預(yù)讀取肚吏，每次把該節(jié)點(diǎn)數(shù)據(jù)讀取出來并存儲到內(nèi)存中
- B-樹中每個(gè)節(jié)點(diǎn)存儲的關(guān)鍵詞變多，導(dǎo)致存儲相同數(shù)量的數(shù)據(jù)狭魂，B-樹的深度相比平衡二叉樹深度更淺罚攀，減少了數(shù)據(jù)的查找次數(shù)和復(fù)雜度
B+樹對比紅黑樹
- 紅黑樹多用于內(nèi)部排序，即全放在內(nèi)存中
- B+樹多用于外存上時(shí)雌澄，B+也被成為一個(gè)磁盤友好的數(shù)據(jù)結(jié)構(gòu)
- 紅黑樹和平衡二叉樹有相同缺點(diǎn)斋泄，每個(gè)節(jié)點(diǎn)存儲一個(gè)關(guān)鍵詞，數(shù)據(jù)量大時(shí)镐牺，導(dǎo)致紅黑樹的深度很深炫掐，mysql每次讀取時(shí)消耗大量io
B+樹相比B-樹的優(yōu)點(diǎn)
- B+樹非葉子節(jié)點(diǎn)只存儲key值，而B-樹存儲key值和data值睬涧，這樣B+樹每次讀取時(shí)可以讀取到更多的key值
- mysql進(jìn)行區(qū)間訪問時(shí)卒废，由于B+樹葉子節(jié)點(diǎn)之間用指針相連，只需要遍歷所有的葉子節(jié)點(diǎn)即可宙地；而B-樹則需要中序遍歷那樣遍歷
- B+樹非葉子節(jié)點(diǎn)只存儲key值摔认，而B-樹存儲key值和data值，導(dǎo)致B+樹的層級更少宅粥，查詢效率更高
- B+樹所有關(guān)鍵詞地址都存在葉子節(jié)點(diǎn)上参袱，所以每次查詢次數(shù)都相同，比B-樹穩(wěn)定
為什么高度為3的B+樹存儲千萬級數(shù)據(jù)？
解釋這個(gè)問題的前提抹蚀，mysql使用InnoDB引擎剿牺，mysql默認(rèn)頁文件大小為16k
假設(shè)我們一行數(shù)據(jù)大小為1k，那么一頁存儲16條數(shù)據(jù)环壤，也就是說一個(gè)葉子節(jié)點(diǎn)能存儲16條數(shù)據(jù)
再來看看非葉子節(jié)點(diǎn)晒来，假設(shè)主鍵ID為bigint類型，那么長度為8B郑现，指針大小在InnoDB引擎中的大小為6B湃崩，一共14B，那么一頁中可以存放16k/14B=1170個(gè)(主鍵+指針)
也就是說高度為2的B+樹可以存儲的數(shù)據(jù)為:117016=18720條接箫；高度為3的B+樹可以存儲的數(shù)據(jù)為:11701170*16=21902400(千萬條數(shù)據(jù))
這也是為什么mysql可以支撐千萬級別數(shù)據(jù)的原因
文章也會持續(xù)更新攒读，可以微信搜索「 邁莫coding 」第一時(shí)間閱讀。
