數據庫索引采用B樹和B+樹的原因是什么

本篇內容介紹了“數據庫索引采用B樹和B+樹的原因是什么”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

我們以拋出問題的形式開始講解：

（1）數據庫文件存儲的方式

數據庫文件存儲都是以磁盤文件存儲在系統中的，這也是數據庫能持久化存儲數據的原因。

（2）從數據庫讀取數據的原理

從數據庫讀取數據，先暫且不考慮從緩存中讀取數據的情況，那就是從磁盤文件中讀取數據的，我們知道從磁盤文件中讀取數據是比較耗時的，數據庫的select操作的時間，取決于執行磁盤IO的次數，因此盡量減少磁盤IO就可以顯著的提升數據的查詢速度。

（3）減少磁盤IO操作的影響因素

有哪些因素可以減少磁盤IO呢，這首先得將了解一下磁盤IO與預讀。

磁盤IO與預讀

磁盤讀取依靠的是機械運動，分為尋道時間、旋轉延遲、傳輸時間三個部分，這三個部分耗時相加就是一次磁盤IO的時間，大概9ms左右。這個成本是訪問內存的十萬倍左右；正是由于磁盤IO是非常昂貴的操作，所以計算機操作系統對此做了優化：預讀；每一次IO時，不僅僅把當前磁盤地址的數據加載到內存，同時也把相鄰數據也加載到內存緩沖區中。

因為局部預讀原理說明：當訪問一個地址數據的時候，與其相鄰的數據很快也會被訪問到。每次磁盤IO讀取的數據我們稱之為一頁（page）。一頁的大小與操作系統有關，一般為4k或者8k。這也就意味著讀取一頁內數據的時候，實際上發生了一次磁盤IO。

正因為有了磁盤IO預讀機制，所以才有了減少磁盤IO的可能，因為一次磁盤IO操作，可以查找到物理存儲中相鄰的一大片數據。

以索引為B+樹為例：

磁盤IO次數和索引數據結構查詢的次數以及磁盤IO與預讀都有關系，具體關系：磁盤IO次數 <= B+樹中從根節點一直到葉子節點整個過程中查詢的節點數。

一次磁盤IO操作可以取出物理存儲中相鄰的一大片數據，如果查詢的索引數據（就是B+樹中從根節點一直到葉子節點整個過程中查詢的節點數）都集中在該區域，那么只需要一次磁盤IO，否則就需要多次磁盤IO

（4）基于磁盤IO預讀機制，索引可以快速查詢數據

到現在才開始講解索引了。正是基于磁盤IO預讀機制的前提，數據庫可以采用索引機制快速查詢出數據。

（a）什么是索引

索引是幫助數據高效查詢數據的一種數據結構，它包含一個表中某些列的值以及記錄對應的地址，并且把這些值存儲在一個數據結構中。常用的索引有B樹和B+樹

（b）為什么要使用索引

舉個例子來說，假設我們有一個數據庫student，這個表分別有三個字段：name，age，class。假設表中有2000條記錄。

1、假如沒有使用索引，當我們查詢名為“xiaxia”的學生的時候，即調用：

select name,age,class from student where name = "xiaxia";

此時數據庫不得不在student表中對這2000條記錄一條一條的進行判斷name字段是否為“xiaxia”。這也就是所謂的全表掃描。

2、而當我們在student表上的name字段上創建索引時，當我們查詢名為“xiaxia”的學生時：

會通過索引查找去查詢名為“xiaxia”的學生，因為該索引已經按照字母順序排列，因此要查找名為“xiaxia”的記錄時會快很多，因為名字首字母為“x”的雇員都是排列在一起的。通過該索引，能獲取到表中對應的記錄。

（5）數據庫中使用什么數據結構作為索引

（a）鏈表

鏈表的查詢速度是O（N），每次查詢都得從鏈表頭開始查詢，例如上面查詢“xiaxia”，如果xiaxia在1000的位置，那么需要遍歷1000次才能查找到。

（b）數組

有人可能會說，查詢速度肯定是數據最快呀，畢竟O（1），的確單純就select的話，采用數組的形式是最合適的，但是采用數組會遇到如下幾個問題：

1、采用數組的話，其他操作如Delete、Update、Insert就不合適了；

2、另外一個原因：索引是存在于磁盤中，當索引非常大的時候，達到幾個G的時候，無法一次加載到內存中。

（c）平衡二叉樹

二叉查找樹查詢的時間復雜度是O（logN），查找速度最快和比較次數最少，既然性能已經如此優秀，但為什么實現索引是使用B-Tree而不是二叉查找樹，關鍵因素是磁盤IO的次數。

（d）B樹和B+樹

數據庫索引采用的數據結構

（6）采用平衡二叉樹和B樹，數據查詢的對比

二叉樹查詢過程：

我們先來看二叉樹查找時磁盤IO的次：定義一個樹高為4的二叉樹，查找值為10：

第一次磁盤IO：

第二次磁盤IO：

第三次磁盤IO:

第四次磁盤IO：

從二叉樹的查找過程了來看，樹的高度和磁盤IO的次數都是4，所以最壞的情況下磁盤IO的次數由樹的高度來決定。

從前面分析情況來看，減少磁盤IO的次數就必須要壓縮樹的高度，讓瘦高的樹盡量變成矮胖的樹，所以B-Tree就在這樣偉大的時代背景下誕生了。

B-Tree查詢過程：

如下有一個3階的B樹，觀察查找元素21的過程：

第一次磁盤IO：

第二次磁盤IO：

這里有一次內存比對：分別跟3與12比對

第三次磁盤IO:

B樹的查詢次數少于平衡二叉樹！所以基于B樹以及B+樹的查詢次數少于平衡二叉樹。

“數據庫索引采用B樹和B+樹的原因是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！