資料庫索引以及索引的實作(B+樹介紹，和B樹，差別）

資料庫索引以及索引的實作(B+樹介紹，和B樹，差別）

索引

索引是提高資料庫表通路速度的方法。

分為聚集索引和非聚集索引。

聚集索引：對正文内容按照一定規則排序的目錄。

非聚集索引：目錄按照一定的順序排列，正文按照另一種順序排列，目錄與正文之間保持一種映射關系。

把資料庫索引比作字典查詢索引，

聚集索引就是按照拼音查找，拼音欄中字的順序就是查找得到的字的順序。

非聚集索引就像按照偏旁部首查找，同是單人旁查到的字所在的頁碼可能是雜亂的，沒有順序的。

存儲結構

記憶體中存儲的資料是有限的，當需要在磁盤中進行查找時就涉及到了磁盤的 I/O 操作。

當磁盤驅動器執行讀/寫功能時。盤片裝在一個主軸上，并繞主軸高速旋轉，當磁道在讀/寫頭(又叫磁頭) 下通過時，就可以進行資料的讀 / 寫了。磁盤讀取資料是以盤塊(block)為基本機關的。位于同一盤塊中的所有資料都能被一次性全部讀取出來。而磁盤IO代價主要花費在查找時間Ts上。是以我們應該盡量将相關資訊存放在同一盤塊，同一磁道中。或者至少放在同一柱面或相鄰柱面上，以求在讀/寫資訊時盡量減少磁頭來回移動的次數，避免過多的查找時間。

索引查找時産生磁盤I/O消耗，相對于記憶體存取，I/O存取的消耗要高幾個數量級，是以評價一個資料結構作為索引的優劣最重要的名額就是在查找過程中磁盤I/O操作次數的時間複雜度。樹高度越小，I/O次數越少。

平衡樹的高度過深進行多次磁盤IO，導緻查詢效率低下，而B樹和B+樹樹中每個結點最多含有m個孩子，是以相對平衡樹B樹和B+樹的高度比較低。

B樹 

每個節點都存儲key和data，所有節點組成這棵樹，并且葉子節點指針為null。

B+樹 

隻有葉子節點存儲data，葉子節點包含了這棵樹的所有鍵值，葉子節點不存儲指針。所有非終端節點看成是索引，節點中僅含有其子樹根節點最大（或最小）的關鍵字，不包含查找的有效資訊。B+樹中所有葉子節點都是通過指針連接配接在一起。

總結：為什麼使用B+樹？

1.檔案很大，不可能全部存儲在記憶體中，故要存儲到磁盤上 

2.索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數（為什麼使用B-/+Tree，還跟磁盤存取原理有關，具體看下邊分析） 

3. 局部性原理與磁盤預讀，預讀的長度一般為頁（page）的整倍數，（在許多作業系統中，頁得大小通常為4k） 

4. 資料庫系統巧妙利用了磁盤預讀原理，将一個節點的大小設為等于一個頁，這樣 每個節點隻需要一次I/O 就可以完全載入，(由于節點中有兩個數組，是以位址連續)。而紅黑樹這種結構， h 明顯要深的多。由于邏輯上很近的節點（父子）實體上可能很遠，無法利用局部性。

為什麼B+樹比B樹更适合做索引？

1.B+樹磁盤讀寫代價更低 

B+的内部結點并沒有指向關鍵字具體資訊的指針，即内部節點不存儲資料。是以其内部結點相對B 樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。

2.B+-tree的查詢效率更加穩定 

由于非終結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。

在MySQL中，最常用的兩個存儲引擎是MyISAM和InnoDB，它們對索引的實作方式是不同的。

MyISAM data存的是資料位址。索引是索引，資料是資料。

InnoDB data存的是資料本身。索引也是資料。

原文位址 https://blog.csdn.net/xiao_ma_CSDN/article/details/80773724