3分鐘了解數據庫索引知識「數據庫索引是什麼數據類型」

前言

你知道索引長什麼樣嗎？

當磁盤剩餘空間較小時，為什麼我們加了索引會導致磁盤空間不足？

為什麼多加了幾個索引，mysql 插入和刪除的效率反而下降了呢？

帶着這些問題，我們開始今天的話題。

什麼是索引？

索引（Index）是幫助數據庫系統高效獲取數據的數據結構，數據庫索引本質上是以增加額外的寫操作與用於維護索引數據結構的存儲空間為代價的用於提升數據庫中數據檢索效率的數據結構。

總結一下就是，索引就是數據結構！！一種為了提升檢索效率的數據結構。

常見的數據庫的索引有：hash 表、B+樹等。

那索引物理上是怎麼表現的呢？其實我們上一篇《mysql的數據到底是怎麼存的（下）|mysql系列（5）》中講到：MySQL 的存儲結構分為 5 級：表空間、段、簇、頁、行。創建一個索引就會創建兩個段：一個數據段、一個索引段。

InnDB的索引為什麼是B+樹？

二叉樹的查找效率也非常高，比如平衡二叉樹，我們在數據結構和算法中經常會用到二叉樹的思想來解決問題，我們都知道mysql用的是B+樹，那麼為什麼InnDB 不用二叉樹呢？

因為平衡二叉樹這種結構在內存裏面的查找效率是比較快的。但是

索引是存在於索引文件中，是存在於磁盤中的。因為索引通常是很大的，因此無法一次將全部索引加載到內存當中，因此每次只能從磁盤中讀取一個磁盤頁的數據到內存中。而這個磁盤的讀取的速度較內存中的讀取速度而言是差了好幾個級別。

因為二叉樹序列化到磁盤的時候，其物理實現是數組，具體可以參考

《一文搞定二叉樹—由二叉樹到貪心算法》

然後由於在邏輯結構上相近的節點在物理結構上可能會差很遠。因此，每次讀取的磁盤頁的數據中有許多是用不上的。因此，查找過程中要進行許多次的磁盤讀取操作。

二叉樹做索引有什麼問題？

二叉樹應用在磁盤這類的搜索那麼會有以下幾個問題:

• 數據非常大時, 樹高度會很高, 造成磁盤io掃描次數很高
• 一個節點只是存放一個數據, 數據與數據之間在物理內存相隔甚遠, 磁盤掃描需要頻繁轉動
• 需要頻繁的從磁盤讀數據到內存中, 即使操作系統有預讀, 但是帶出來的大多是暫時用不上的無用數據, 造成浪費

這裡我們複習一下幾個知識點：

磁盤IO時間：

• 磁盤IO時間 = 尋道 + 磁盤旋轉 + 數據傳輸時間

機械硬盤的連續讀寫和隨機讀寫的性能差異：

• 順序訪問：內存訪問速度是硬盤訪問速度的6~7倍（kafka的特點，以後有機會的話再講一講）
• 隨機訪問：內存訪問速度就要比硬盤訪問速度快上10萬倍以上隨機讀寫時，磁頭需要不停的移動，時間都浪費在了磁頭尋址上。而在實際的磁盤存儲里，是很少順序存儲的，因為這樣的維護成本會很高。

局部性原理與磁盤預讀：

由於存儲介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個位元組，磁盤也會從這個位置開始，順序向後讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：

當一個數據被用到時，其附近的數據也通常會馬上被使用。

程序運行期間所需要的數據通常比較集中。

由於磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉時間），因此對於具有局部性的程序來說，預讀可以提高I/O效率。

總結一句話：由於磁盤的存儲及訪問的特性及二叉樹的物理存儲方式導致二叉樹在磁盤上的查詢速度很慢，不適合做索引。

B+樹的引入

鑒於以上幾個問題, 有以下幾點需要優化的:

• 減少磁盤io掃描次數。
• 減少磁盤io轉動頻率。
• 利用好操作系統的預讀, 局部性原理。

B樹是為了充分利用磁盤預讀功能來而創建的一種數據結構，也就是說B樹就是為了作為索引才被發明出來的的。

B+ 樹的特點

• b+樹擁有b樹的所有優點, 並且b+樹的非葉子節點不存放數據, 而是單單存放索引, 只有在葉子節點存放索引+數據, 並且葉子節點通過前後指針構成雙向鏈表的結構, 因此通過樹結構定位到索引後, 可以通葉子節點的鏈表指針很快的直接遍歷得到範圍查詢的結果 這樣更好的利用了順序io比隨機io性能更高的優化. 這個特點是b樹不具備的.
• b+樹是innodb的底層數據結構, 通過N叉樹, 節點頁, 葉子節點鏈表串起來, 避免了過多的磁盤io掃描, 轉動次數, 並且利用了操作系統的預讀和局部性原理, 更支持了範圍查詢的功能.

B+ 樹的優點

• B樹/B+樹與紅黑樹、平衡二叉樹等二叉樹相比，最大的優勢在於樹高更小。
• Innodb中每個節點使用一個頁(page)，頁的大小為16KB，其中元數據只佔大約128位元組左右(包括文件管理頭信息、頁面頭信息等等)，大多數空間都用來存儲數據。
• 對於一顆3層B+樹，第一層(根節點)有1個頁面，可以存儲1000條記錄；第二層有1000個頁面，可以存儲1000*1000條記錄；第三層(葉節點)有1000*1000個頁面，每個頁面可以存儲100條記錄，因此可以存儲1000*1000*100條記錄，即1億條。而對於二叉樹，存儲1億條記錄則需要26層左右。

總結一下

現在我們可以回答開頭的幾個問題了。

InnoDB 就是一個B+樹的數據結構。

每加一個索引就會生成兩個文件，所以當服務器磁盤空間少時加了索引會導致磁盤空間不足。

索引多的話，每次添加刪除數據都會維護多個文件，效率反而降低。