相信很多程序員朋友對數據的索引并不陌生，最常見的索引是 B+ Tree 索引，索引可以加快數據庫的檢索速度，但是會降低新增、修改、刪除操作的速度，一些錯誤的寫法會導致索引失效等等。

但是如果被問到，為什么用了索引之后，查詢就會變快？B+ Tree 索引的原理是什么？這時候很多人可能就不知道了，今天我就以 MySQL 的 InnoDB 引擎為例，講一講 B+ Tree 索引的原理。

索引的基礎知識

MySQL 的基本存儲結構是頁，大概就是這個樣子的：

在這里，我們需要了解以下幾點（非常重要）：

• 當我們用 MySQL 的 InnoDB 引擎創(chuàng)建表，有且只能有一個主鍵；如果我們沒有顯示地指定之間，那么MySQL 會自動生成一個隱含字段作為主鍵；

• 聚集索引：以主鍵創(chuàng)建的索引；聚集索引的葉子節(jié)點存儲的是表中的數據；

• 非聚集索引：非主鍵創(chuàng)建的索引；非聚集索引在葉子節(jié)點存儲的是主鍵和索引列；使用非聚集索引查詢數據，會查詢到葉子上的主鍵，再根據主鍵查到數據（這個過程叫做回表）。

頁和頁之間、頁和數據之間的關系

我們以聚集索引做講解，頁和頁之間、以及頁和數據之間的關系是這樣的：

• 數據頁和數據頁之間，組成一個雙向鏈表；

• 每個數據頁中的記錄，是一個單向鏈表；

• 每個數據頁都根據內部的記錄生成一個頁目錄（Page directory），如果是主鍵的話，可以在頁目錄中使用二分法快速定位；

• 如果我們根據一個非主鍵、非索引列進行查詢，那么需要遍歷雙向鏈表，找到所在的頁；再遍歷頁內的單向鏈表；如果表內數據很大的話，這樣的查詢就會很慢。

B+ Tree 索引的原理

先讓我們看看 B+ Tree 索引大概是什么樣子（以聚集/主鍵索引為例）：

• 假如這時候我們要查詢 id = 16 的數據：

• 查詢頁-1，找到頁-2 存儲的是小于 30 的數據；

• 查詢頁-2，找到頁-5 存儲的是 10~20 的數據；

• 查詢頁-5，找到 id = 16 的數據。

很顯然，沒有用索引的時候，需要遍歷雙向鏈表來定位對應的頁，而有了索引，則可以通過一層層“目錄”定位到對應的頁上。

為什么 B+ Tree 索引會降低新增、修改、刪除的速度

• B+ Tree 是一顆平衡樹，如果對這顆樹新增、修改、刪除的話，會破壞它的原有結構；

• 我們在做數據新增、修改、刪除的時候，需要花額外的時間去維護索引；

• 正因為這些額外的開銷，導致索引會降低新增、修改、刪除的速度。

思考題，歡迎留言討論

現在你是否理解了 B+ Tree 索引的原理？

最后再留一個思考題：為什么官方建議使用自增長主鍵作為索引？大家可以在留言中寫下你的答案。

我將持續(xù)分享Java開發(fā)、架構設計、程序員職業(yè)發(fā)展等方面的見解，希望能得到你的關注；關注我后，可私信發(fā)送數字【1】，獲取海量學習資料。

索引是存儲引擎用于快速查找記錄的數據結構，MySQL 數據庫內部索引是由不同的引擎實現的，主要說一下最常用的InnoDB引擎中的索引，InnoDB引擎中的索引是使用B+ 樹的結構來存儲的，B+ 樹結構如下圖：

先來說一下B+ 樹的特點：

• 葉子節(jié)點（最下面一層）存儲關鍵字（索引字段的值）信息及對應的全部數據記錄。

• 非葉子節(jié)點只存儲關鍵字的信息及子節(jié)點的指針。

• 每個葉子節(jié)點相當于MySQL中的一個數據頁，同層級的葉子節(jié)點以雙向鏈表的形式連接。

• 每個節(jié)點中存儲了多條記錄，記錄之間用單鏈表的形式連接組成了一條有序的鏈表。

• 在 B+ 樹中檢索數據時：每次檢索都從根節(jié)點開始，一直搜索到葉子節(jié)點。

InnoDB 的數據是按數據頁為單位來讀寫的。也就是說，當需要讀取一條記錄的時候，并不是將這個記錄本身從磁盤讀取出來，而是以頁為單位，將整個也加載到內存中，一個頁中可能有很多記錄，然后在內存中對頁通過二分法進行檢索。在InnoDB 中，每個頁的大小默認是16kb。

總體來說，MySQL中的索引用到了B+樹、鏈表、二分法，實現了快速查找數據。

MySQL索引類型

InnoDB 中有兩種索引類型：主鍵索引與輔助索引。

• 主鍵索引（聚集索引）：每個表只有一個主鍵索引，葉子節(jié)點同時保存了主鍵的值以及對應的全部記錄。

• 輔助索引（非聚集索引）：葉子節(jié)點保存了索引字段的值以及主鍵的值。

我們以上圖中Person表 為例，其中id 是主鍵，name 是輔助索引，接下里我們來看一下InnoDB引擎中數據檢索過程：

• 若需要查詢 id=1 的數據，只需要使用主鍵索引中檢索就可以查詢到數據。（紅色線）
  

• 若需要搜索 name='Jacy' 的數據，需要使用非聚集索引與聚集索引，需要2步（藍色線）：
  

1. 先通過輔助索引中檢索 name='Jacy'的數據，獲取 id 的值。

2. 再通過id值 到主鍵索引中 檢索id=12的數據。

接下來，我們再看下以下查詢的數據檢索過程。

主鍵索引（或唯一索引）查詢

上圖中所有的數據都是唯一的，我們查詢26的記錄，過程如下：

• 首先把page1 頁加載到內存中通過二分法查找。

• 確定26位于[20,40)中間，然后加載20所關聯的page3 頁.

• 將page3 頁加載到內存中，采用二分法找到26的記錄后退出。

非唯一索引查詢

上圖中查詢26的所有記錄，數據不唯一，過程如下：

• 將page1 頁加載到內存中通過二分法查找。

• 確定26位于[20,40)中間，然后加載20所關聯的page3 頁。

• 將page3 頁加載到內存中通過二分法找到最后一個小于26的記錄是23，然后通過鏈表從23開始向后訪問，找到所有的26記錄，直到遇到第一個大于26的值退出。

模糊查詢

上圖中查詢以 b字母開頭的所有記錄，過程如下：

• 將page1頁加載到內存中，通過二分法查找最后一個小于等于b的值(b)，和第一個大于b的(z)，b指向葉節(jié)點page3，z指向葉節(jié)點page5。

• 如此一來，可以確定以 b 開頭的記錄存在于[page3,page5) 這個范圍內。

• 最后依次加載page3 到內存中，通過二分法找到第一條b開頭的記錄，然后以鏈表方式繼續(xù)向后訪問page4 中的記錄，直至遇到一個字母為z的值退出。

當我們使用 '%b%' 全模糊查詢時，通過索引我們還可以快速定位所在的頁嘛？

如上圖包含b字母的數據在每個頁中都存在，因此無法判斷包含 b 的記錄在哪些頁中，只能通過IO的方式加載所有頁，遍歷所有記錄進行過濾，才可以找到包含b的記錄。因此使用LIKE %b%進行全模糊查詢時，索引是無效的。

更多內容可以瀏覽《MySQL數據庫中如何正確的理解與使用索引》https://www.toutiao.com/i6759910720944472588/

這個問題和線性查詢、二分查詢是有很大關系的。索引后的數據可以使用二分法查詢，未索引的數據查詢需要線性查詢。下面詳細說一下這兩者之間的性能區(qū)別。

1、兩者的查詢原理

①、線性查詢

線性查詢又稱順序查詢，它的查詢原理就是從第一條記錄開始，逐個比較要查找的字段，直到字段內容和查找值相等，則查找成功，返回結果。若比較結果與字段所有記錄都不等，則查找失敗。下面舉例說明：

需要在某個記錄數為N的數組a[]中查找元素k，那么，線性查詢就是從a[1]開始和k進行對比，對比相等則返回a[i]，如果，不相等則繼續(xù)下一個查詢， i=i+1。直到 i=N為止。那線性查詢的性能就一目了然：

• 最好的情況就是對比1次就找到結果。
• 最差的情況就是需要對比N次才能找到結果。
• 平均計算，就是N/2次能找到結果。

②、二分查詢

二分法查詢也可以說是分段查詢。主要原理就是對已經排序的一組數據進行中間分段，中間分界點和查詢值對比。如果數值小于分界點，則要查找的數落在前半段；如果數字大于分界點，則要查找的數落在前半段；如果等于分界點，則要查找數就已經找到。下面同樣舉例說明：

需要在某個記錄數為N且已經排好序的數組a[]中查找元素K，那么，二分查詢首先是確定數組的中點a[x]，其實也就是a[N/2]這個值（N/2采用進一法取整）。然后對比a[x]和K值，按照前面的方法循環(huán)縮小對比的區(qū)間，最終找到想要的值。二分查詢的性能如下：

• 二分法查詢N條記錄需要log2（N）次對比就能找到結果。
• 前提是：數組必須要排好序

★從上面兩種查詢法原理可以看到，當數組N比較大時，二分查詢的查詢性能明顯優(yōu)于線性查詢。當數組N較小時，則線性查詢的性能更好，因為它少了求中值的開銷。

2、索引給數據庫查詢帶來的性能變化

數據庫中建立索引其實就是對數據庫表中一列或多列的值進行排序的結構。其實就是為了給二分查詢做好排序的前提。結合前面兩種查詢的原理，我們就很容易理解數據庫中索引變快的原因了。其實，數據庫通常情況下，數據量都是比較大的，一般都是上萬條，甚至達到億級記錄。我們用前面原理中的公式計算對比一下：

• 在10萬條記錄中查找一個值：那么，N=100000；
• 線性查詢性能=N/2，計算可得，平均需要對比50000次;
• 二分查詢性能=log2(N)，計算可得，大約需要17次；

從上面計算對比，我們可以看到，索引好了用二分查詢的性能會比線性查詢快非常多。

3、數據庫哪里應該加索引

雖然加了索引后，查詢性能提升很多。但是在數據庫里面也是不所有字段都加索引的，因為，數據庫的整體性能不僅需要考慮查詢性能，還需要考慮寫入性能。當你在數據庫中某個字段加入索引后，該字段就需要建立對應的索引指針。每次新寫入或者修改字段的記錄，都需要額外寫入索引指針。所以，在數據庫中，加入索引會加快搜索性能，但也會相應降低一點點寫入性能。所以，數據庫中建立索引一般在以下幾種情況建立索引。

• 經常需要搜索的列，增加索引可以加快搜索速度；
• 作為主鍵的列，強制該列的唯一性和組織表中數據的排列結構；
• 在經常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度；
• 在經常需要根據范圍進行搜索的列上創(chuàng)建索引，因為索引已經排序，其指定的范圍是連續(xù)的
• 在經常需要排序的列上創(chuàng)建索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間
• 在經常使用在WHERE子句中的列上面創(chuàng)建索引，加快條件的判斷速度

總結

總之，數據庫中因為存在大量的數據，建立索引相當于對數據進行了排序，可以使用二分查詢法來查詢數據，確實會大大提高查詢的速度。但是也會相應降低一點點寫入的速度，所以，數據庫中的索引也是有針對性的建立索引的。

感謝閱讀！我是數智風，用經驗回答問題，歡迎評論關注。

想想漢語字典的拼音和部首索引就可以了，就是這么簡單。

很高興能夠看到和回答這個問題！

什么是數據庫索引？

數據庫中的索引類似于書籍中的目錄，目錄可以快速獲取信息，而不需要閱讀整本書。

在數據庫中，索引可以讓數據庫程序在不掃描整張表的情況下找到所需的數據。本書包含一組章節(jié)，并列出包含章節(jié)的頁碼。數據庫中的索引是表中一列或多列中的一組值，相應的索引列表代表這些值。

索引字段可以是單個字段也可以是多個字段的組合，如果是多個字段的組合，其索引值的排列首先按第一個字段值進行排列，如果其值相同，再按第二個字段的值進行排列，以此類推。

使用索引的意義有哪些？

數據庫中的糖指數類似于書中的目錄值，用于提高信息檢索速度。

使用索引搜索數據不需要掃描整個表格，也不需要快速搜索數據。

索引使用的成本

糖指數需要占據物理內存之外的位置。創(chuàng)建和運行索引需要一定的時間。

?更新索引表時，服務數據重建的速度要放慢。

數據庫索引類別

索引不需要重新排列文件中記錄的順序。一個文件可以有多個相互關聯的索引，每個索引支持鍵碼，通過索引可以快速訪問文件中的記錄。

1、靜態(tài)索引

靜態(tài)索引是在創(chuàng)建文件時創(chuàng)建的索引結構。文件完成后，只有在重新組織時才能修改。2、動態(tài)索引

動態(tài)索引是在創(chuàng)建文件時創(chuàng)建的索引結構。當執(zhí)行插入和刪除等操作時，索引結構本身會發(fā)生變化。

索引的缺點

在添加、修改、刪除數據時，需要維護索引樹，有一定的性能影響。當頻繁維護樹B時，分頁和整合會產生大量的索引碎片，同時需要維護索引的有效性；但存在一個問題也需要注意。

在一段時間內發(fā)生索引（主要是添加、修改、刪除數據。如果頁面已經完成，則需要對頁面進行分割，頻率分開，導致索引碎片增多），從而導致索引頁面分割。這樣會導致隨機訪問I/O文件，而不是按照I/O的順序進行讀取，所以對索引的訪問速度會比較慢。如果碎片數量太多，數據庫可能不會使用索引（太慢，數據庫會選擇更高效的執(zhí)行計劃）。

如何更好地使用數據庫索引

索引字段非常小，最好有一個值，如整個值，如INT；對于經常變化的字段，盡量不要創(chuàng)建索引，索引管理成本很高，生成索引碎片比較容易；如定期索引管理，修正索引碎片；不創(chuàng)建或維護不必要的重復索引，會增加數據變化（添加、修改、刪除）的成本。使用唯一的高字段創(chuàng)建索引，不能在弱字段如樓層中創(chuàng)建索引。

在SQL句子In中，盡量不要使用函數、運算符或表達式來計算where，這可能會導致索引的錯誤使用；必須避免在子空間語句中包含空值，否則會導致引擎在表被完全掃描時停止使用索引；你應該避免在句子中使用任何! =或<<，否則會導致引擎停止使用索引來掃描表。

以上便是我的一些見解和回答，可能不能如您所愿，但我真心希望能夠對您有所幫助！不清楚的地方您還可以關注我的頭條號“每日精彩科技”我將竭盡所知幫助您！

碼字不易，感覺寫的還行的話，還請點個贊哦！

目錄結構數據一定少于內容數據

以查字典為例，來說明這個問題。

先想象一下有一本字典，里面的字是隨意排列的，我們要查一個字，就只能一頁一頁翻過去查找，這樣下來查一個字就會花很多時間，如果運氣不好，我們要找的字在最后一頁，就得翻幾千頁了。用數據庫的術語叫遍歷（full scan）。

為了縮短查詢時間，我們把字典里的字按照拼音字母的順序排列好。這樣查字的時候，查看一下中間那一頁，就可以知道我們要查的字是在前面還是在后面。比如在前面，我們就查看1/4處的那一頁，如此反復直到我們找到要查的字為止。那么這么做我們得查多少次呢？一本六萬多頁的字典最多查16次就能找到您想要的那一頁了。這種方法要比遍歷的方法快得多。用數據庫的術語叫B-TREE(二叉樹)。

如果我們不知道發(fā)音想按部首查字典又該怎么辦呢？字典里按照部首的順序做了個表，查這個表就可以快速查到解釋那個字的頁碼了。這個表用數據庫的術語就叫索引。

數據庫里的數據經常會有千萬條以上，雙十一某寶的數據，一分鐘的交易數據大概就能突破千萬。這么大量的數據一條一條遍歷恐怕是不現實的，在這樣的數據庫里，建立完善的索引是必須的。有了索引以億為單位的數據，也只要做幾十次檢索就足夠了。

值得注意的是，索引是以字段為基礎建立的，在檢索的時候，如果對被索引的字段進行運算，就很可能打亂事前排好的順序，導致不得不遍歷數據，使索引失去效果。

建索引就是 把 數據表 的一個 字段 作為 key,建立查找的表，

插入的時候對索引字段計算哈希值，把哈希值和行號對應關系放進一張哈希表。

查詢的時候對索引字段計算哈希值，從哈希表中查到行號，就能找到這一行了。

用redis的key hash list能模擬一個簡單的帶索引的關系型數據庫。

以空間換時間