mysql索引數(shù)據(jù)結(jié)構(gòu)要用B+樹的原因是什么

這篇文章主要講解了“mysql索引數(shù)據(jù)結(jié)構(gòu)要用B+樹的原因是什么”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“mysql索引數(shù)據(jù)結(jié)構(gòu)要用B+樹的原因是什么”吧！

1. Hash表？No

因考慮到在數(shù)據(jù)檢索的過程中經(jīng)常會(huì)有范圍的查詢（如下），而hash表不能提供這種功能。

SELECT * FROM hero WHERE age>5 AND age<20;

使用哈希算法實(shí)現(xiàn)的索引雖然可以做到快速檢索數(shù)據(jù)，但是沒辦法做數(shù)據(jù)高效范圍查找，因此哈希索引是不適合作為 Mysql 的底層索引的數(shù)據(jù)結(jié)構(gòu)。

2. 二叉查找樹(BST)？No

二叉查找樹（Binary Search Tree）雖然可以達(dá)到范圍搜索，但是在樹的插入過程中，如果插入的數(shù)據(jù)本來就是有順序的，那么就會(huì)形成一條鏈（如下），它的最壞情況是O(n)。 

3. 紅黑樹？No

紅黑樹雖然看似達(dá)到了平衡狀態(tài)，但是也會(huì)有極端情況存在，和上述BST樹一樣，雖然不會(huì)成為鏈狀，但是紅黑樹會(huì)存在右傾的現(xiàn)象。 

在數(shù)據(jù)庫中的基本主鍵自增操作，主鍵一般都是數(shù)百萬數(shù)千萬的，如果紅黑樹存在這種問題，對(duì)于查找性能而言也是巨大的消耗，我們數(shù)據(jù)庫不可能忍受這種無意義的等待的。

4. 平衡二叉樹(AVL)？差那么二點(diǎn)意思

平衡二叉樹，英文翻譯為Balanced Binary Tree，為啥叫AVL呢？ AVL 是大學(xué)教授G.M. Adelson-Velsky 和 E.M. Landis 名稱的縮寫，他們提出的平衡二叉樹的概念，為了紀(jì)念他們，將平衡二叉樹稱為 AVL樹。

AVL樹本質(zhì)上是一顆二叉查找樹，但是它又具有以下特點(diǎn)：

• 它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，

• 左右兩個(gè)子樹也都是一棵平衡二叉樹。

它不存在紅黑樹這種右傾的現(xiàn)象，也具備數(shù)據(jù)高效范圍查找的能力，但是數(shù)據(jù)庫查詢數(shù)據(jù)的瓶頸在于磁盤的IO，樹節(jié)點(diǎn)在磁盤空間中存儲(chǔ)可能是不連續(xù)的，假設(shè)我們一次IO讀取一個(gè)樹的節(jié)點(diǎn)，此次讀入內(nèi)存的這頁中沒有其他樹的節(jié)點(diǎn)，那么每讀取一個(gè)樹的節(jié)點(diǎn)，就要進(jìn)行一次IO，這是多么消耗時(shí)間啊，所以我們?cè)O(shè)計(jì)數(shù)據(jù)庫索引時(shí)需要首先考慮怎么盡可能減少磁盤 IO 的次數(shù)。 磁盤讀取依靠的是機(jī)械運(yùn)動(dòng)，分為尋道時(shí)間、旋轉(zhuǎn)延遲、傳輸時(shí)間三個(gè)部分，這三個(gè)部分耗時(shí)相加就是一次磁盤IO的時(shí)間；這個(gè)花費(fèi)的時(shí)間成本是內(nèi)存訪問的十幾萬倍左右。 正是由于磁盤IO是非常昂貴的操作，所以計(jì)算機(jī)操作系統(tǒng)對(duì)此做了優(yōu)化：預(yù)讀；每一次IO時(shí)，不僅僅把當(dāng)前磁盤地址的數(shù)據(jù)加載到內(nèi)存，同時(shí)也把相鄰數(shù)據(jù)也加載到內(nèi)存緩沖區(qū)中。因?yàn)榫植款A(yù)讀原理說明：當(dāng)訪問一個(gè)地址數(shù)據(jù)的時(shí)候，與其相鄰的數(shù)據(jù)很快也會(huì)被訪問到。每次磁盤IO讀取的數(shù)據(jù)我們稱之為一頁（page）。一頁的大小與操作系統(tǒng)有關(guān)，一般為4k或者8k。這也就意味著讀取一頁內(nèi)數(shù)據(jù)的時(shí)候，實(shí)際上發(fā)生了一次磁盤IO。

相關(guān)術(shù)語解釋：

扇區(qū)(sector)：

• 磁盤上的每個(gè)磁道被等分成多個(gè)弧段，這個(gè)弧段便稱作扇區(qū)（sector）。

• 扇區(qū)是磁盤物理層面的名稱，它是實(shí)際發(fā)生讀寫的最底層。

磁盤塊(IO Block)：

• 操作系統(tǒng)不與扇區(qū)直接進(jìn)行交互，因?yàn)橐话闱闆r下一個(gè)扇區(qū)是512byte，如果1T去用512byte進(jìn)行劃分，那劃分的地址空間太多了，為了讓操作系統(tǒng)能夠?qū)ぶ返礁蟮牡刂房臻g，操作系統(tǒng)將相鄰的扇區(qū)組合在一起，形成一個(gè)塊，對(duì)塊進(jìn)行管理。每個(gè)磁盤塊可以包括 2、4、8、16、32 或 64 個(gè)扇區(qū)，這便是磁盤塊（IO Block）。

• 磁盤塊是操作系統(tǒng)中出現(xiàn)的名稱，文件系統(tǒng)讀寫數(shù)據(jù)的最小單位，它同時(shí)也被叫做磁盤簇。

頁(page)：

• 頁是內(nèi)存中出現(xiàn)的名稱，它是內(nèi)存的最小存儲(chǔ)單位，頁的大小通常為磁盤塊大小的 2^n 倍。

5. B-tree(B-樹也稱B樹)？差那么一點(diǎn)意思

B樹是一種平衡的多叉樹，B樹相比于平衡二叉樹(AVL)，它能夠在單個(gè)節(jié)點(diǎn)中存儲(chǔ)大量鍵，也降低了樹的高度，從而減少了IO的次數(shù)。 

B樹的節(jié)點(diǎn)中存儲(chǔ)的是數(shù)據(jù)，單個(gè)節(jié)點(diǎn)存儲(chǔ)的內(nèi)容還是太少了，如何讓一個(gè)節(jié)點(diǎn)存儲(chǔ)的內(nèi)容更多呢？B+樹它來了。

6. B+樹

在節(jié)點(diǎn)中存儲(chǔ)某段數(shù)據(jù)的首地址，并且B+樹的葉子節(jié)點(diǎn)用了一個(gè)鏈表串聯(lián)起來，便于范圍查找。 

B+樹高度降低，減少了磁盤 IO。其次，B+樹的葉子節(jié)點(diǎn)是真正數(shù)據(jù)存儲(chǔ)的地方，葉子節(jié)點(diǎn)用了鏈表連接起來，這個(gè)鏈表本身就是有序的，在數(shù)據(jù)范圍查找時(shí)，更具備效率。因此 Mysql 的索引用的就是 B+樹，B+樹在查找效率、范圍查找中都有著非常不錯(cuò)的性能。

感謝各位的閱讀，以上就是“mysql索引數(shù)據(jù)結(jié)構(gòu)要用B+樹的原因是什么”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)mysql索引數(shù)據(jù)結(jié)構(gòu)要用B+樹的原因是什么這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！