天天看點

mysql有使用紅黑樹嗎_為什麼Mysql用B+樹做索引而不用B-樹或紅黑樹

B+樹做索引而不用B-樹

那麼Mysql如何衡量查詢效率呢?– 磁盤IO次數。

一般來說索引非常大,尤其是關系性資料庫這種資料量大的索引能達到億級别,是以為了減少記憶體的占用,索引也會被存儲在磁盤上。

B-樹/B+樹的特點就是每層節點數目非常多,層數很少,目的就是為了減少磁盤IO次數,但是B-樹的每個節點都有data域(指針),這無疑增大了節點大小,說白了增加了磁盤IO次數(磁盤IO一次讀出的資料量大小是固定的,單個資料變大,每次讀出的就少,IO次數增多,一次IO多耗時), 而B+樹除了葉子節點其它節點并不存儲資料,節點小,磁盤IO次數就少。

B+樹的優點

優點一: B+樹的磁盤讀寫代價更低:B+樹隻有葉節點存放資料,其餘節點用來索引,而B-樹是每個索引節點都會有Data域。

優點二: B+樹帶有順序通路指針:B+樹所有的Data域在葉子節點,并且所有葉子節點之間都有一個鍊指針。 這樣周遊葉子節點就能獲得全部資料,這樣就能進行區間通路啦。在資料庫中基于範圍的查詢是非常頻繁的,而B樹不支援這樣的周遊操作。

優點三:B+樹的查詢效率更加穩定:由于非葉子節點并不是最終指向檔案内容的節點,而隻是葉子節點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同,導緻每一個資料的查詢效率相當。而B樹因為非葉子節點也存在資料Data域,有可能在非葉子節點中就可擷取資料并傳回。

B+數帶有順序通路指針的優點

一般在資料庫系統或檔案系統中使用的B+Tree結構都在經典B+Tree的基礎上進行了優化,增加了順序通路指針。在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針,就形成了帶有順序通路指針的B+Tree。做這個優化的目的是為了提高區間通路的性能,例如如果要查詢key為從15到60的所有資料記錄,當找到15後,隻需順着節點和指針順序周遊就可以一次性通路到所有資料節點,極大提到了區間查詢效率。

B樹的優點

對于在内部節點的資料,可直接得到,不必根據葉子節點來定位

B+樹做索引而不用紅黑樹

AVL 樹(平衡二叉樹)和紅黑樹(二叉查找樹)基本都是存儲在記憶體中才會使用的資料結構。

在大規模資料存儲的時候,紅黑樹往往出現由于樹的深度過大而造成磁盤IO讀寫過于頻繁,進而導緻效率低下的情況。

為什麼會出現這樣的情況?

我們知道要擷取磁盤上資料,必須先通過磁盤移動臂移動到資料所在的柱面,然後找到指定盤面,接着旋轉盤面找到資料所在的磁道,最後對資料進行讀寫。磁盤IO代價主要花費在查找所需的柱面上,樹的深度過大會造成磁盤IO頻繁讀寫。根據磁盤查找存取的次數往往由樹的高度所決定,是以,隻要我們通過某種較好的樹結構減少樹的結構盡量減少樹的高度,B樹可以有多個子女,從幾十到上千,但是降低樹的高度。

資料庫設計者選擇

資料庫系統的設計者巧妙利用了磁盤預讀原理,将一個節點的大小設為等于一個頁,這樣每個節點隻需要一次I/O就可以完全載入。為了達到這個目的,在實際實作B-Tree還需要使用如下技巧:每次建立節點時,直接申請一個頁的空間,這樣就保證一個節點實體上也存儲在一個頁裡,加之計算機存儲配置設定都是按頁對齊的,就實作了一個node隻需一次I/O。

B-Tree有許多變種,其中最常見的是B+Tree,例如MySQL就普遍使用B+Tree實作其索引結構。

磁盤和記憶體選擇B樹和紅黑樹的原因

B樹優點

B+樹的高度要比紅黑樹小,有效減少了磁盤的随機通路

B+樹的資料節點互相臨近,能夠發揮磁盤順序讀取的優勢(緩存)

B+樹的資料全部存于葉子結點,而其他節點産生的浪費在經濟負擔上能夠接收,紅黑樹存儲浪費小

紅黑樹優點

紅黑樹常用于存儲記憶體中的有序資料,增删很快,B+樹常用于檔案系統和資料庫索引,因為B樹的子節點大于紅黑樹,紅黑樹隻能有2個子節點,B樹子節點大于2,子節點樹多這一特點保證了存儲相同大小的資料,樹的高度更小,資料局部更加緊湊,而硬碟讀取有局部加載的優化(緊湊的好處:把要讀取資料和周圍的資料一起預先讀取),B樹相鄰資料實體上更加緊湊這一特點符合硬碟進行io優化的特性。

B+樹在B樹基礎上進一步将資料隻存在葉子節點,非葉子節點不存值隻存儲值的指向,這使得單個節點能有更多子節點,除此之外将所有葉子節點(值存在葉子節點)放傳入連結表中,使得資料更加緊湊有序,隻需要連結清單(葉子節點)的一次周遊就能擷取所有樹上的值。

B+樹這些特性适合用于資料庫的索引,mysql底層資料結構就是B+樹。

B樹更适用于磁盤讀取,紅黑樹更适用于記憶體讀取