B+/-Tree原理

B-Tree介紹

B-Tree是一種多路搜索樹（并不是二叉的）：
?????? 1.定義任意非葉子結點最多只有M個兒子；且M>2；
?????? 2.根結點的兒子數為[2, M]；
?????? 3.除根結點以外的非葉子結點的兒子數為[M/2, M]；
?????? 4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
?????? 5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；
?????? 6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
?????? 7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；
?????? 8.所有葉子結點位于同一層；
???????如：（M=3）

?

B-樹的特性：
?????? 1.關鍵字集合分布在整顆樹中；
?????? 2.任何一個關鍵字出現且只出現在一個結點中；
?????? 3.搜索有可能在非葉子結點結束；
?????? 4.其搜索性能等價于在關鍵字全集內做一次二分查找；
?????? 5.自動層次控制；

B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為空，或已經是葉子結點；

B+Tree介紹

B+樹是B-樹的變體，也是一種多路搜索樹：

?????? 1.其定義基本與B-樹同，除了：

?????? 2.非葉子結點的子樹指針與關鍵字個數相同；

?????? 3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區間）；

?????? 5.為所有葉子結點增加一個鏈指針；

?????? 6.所有關鍵字都在葉子結點出現；

???????如：（M=3）

B+的搜索與B-樹也基本相同，區別是B+樹只有達到葉子結點才命中（B-樹可以在非葉子結點命中），其性能也等價于在關鍵字全集做一次二分查找；

?????? B+的特性：

?????? 1.所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的；

?????? 2.不可能在非葉子結點命中；

?????? 3.非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲（關鍵字）數據的數據層；

?????? 4.更適合文件索引系統；

?

mysql中的索引

?

mysql中普遍使用B+Tree做索引，但在實現上又根據聚簇索引和非聚簇索引而不同。

聚簇索引

所謂聚簇索引，就是指主索引文件和數據文件為同一份文件，聚簇索引主要用在Innodb存儲引擎中。在該索引實現方式中B+Tree的葉子節點上的data就是數據本身，key為主鍵，如果是一般索引的話，data便會指向對應的主索引，如下圖所示：

在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序訪問指針的B+Tree。做這個優化的目的是為了提高區間訪問的性能，例如圖4中如果要查詢key為從18到49的所有數據記錄，當找到18后，只需順著節點和指針順序遍歷就可以一次性訪問到所有數據節點，極大提到了區間查詢效率。

非聚簇索

?

非聚簇索引就是指B+Tree的葉子節點上的data，并不是數據本身，而是數據存放的地址。主索引和輔助索引沒啥區別，只是主索引中的key一定得是唯一的。主要用在MyISAM存儲引擎中，如下圖：

非聚簇索引比聚簇索引多了一次讀取數據的IO操作，所以查找性能上會差。

MyisAM索引與InnoDB索引相比較

• MyisAM支持全文索引（FULLTEXT）、壓縮索引，InnoDB不支持；
• InnoDB支持事務，MyisAM不支持；
• MyisAM順序儲存數據，索引葉子節點保存對應數據行地址，輔助索引很主鍵索引相差無幾；InnoDB主鍵節點同時保存數據行，其他輔助索引保存的是主鍵索引的值；
• MyisAM鍵值分離，索引載入內存（key_buffer_size），數據緩存依賴操作系統；InnoDB鍵值一起保存，索引與數據一起載入InnoDB緩沖池；MyisAM主鍵（唯一）索引按升序來存儲存儲，InnoDB則不一定
• MyisAM索引的基數值（Cardinality，show index?命令可以看見）是精確的，InnoDB則是估計值。這里涉及到信息統計的知識，MyisAM統計信息是保存磁盤中，在alter表或Analyze table操作更新此信息，而InnoDB則是在表第一次打開的時候估計值保存在緩存區內；
• MyisAM處理字符串索引時用增量保存的方式，如第一個索引是‘preform’，第二個是‘preformence’，則第二個保存是‘7，ance’，這個明顯的好處是縮短索引，但是缺陷就是不支持倒序提取索引，必須順序遍歷獲取索引

為什么選用B+/-Tree

一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。

簡單點說說內存讀取，內存是由一系列的存儲單元組成的，每個存儲單元存儲固定大小的數據，且有一個唯一地址。當需要讀內存時，將地址信號放到地址總線上傳給內存，內存解析信號并定位到存儲單元，然后把該存儲單元上的數據放到數據總線上，回傳。

寫內存時，系統將要寫入的數據和單元地址分別放到數據總線和地址總線上，內存讀取兩個總線的內容，做相應的寫操作。

內存存取效率，跟次數有關，先讀取A數據還是后讀取A數據不會影響存取效率。而磁盤存取就不一樣了，磁盤I/O涉及機械操作。磁盤是由大小相同且同軸的圓形盤片組成，磁盤可以轉動(各個磁盤須同時轉動)。磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的內容。磁頭不動，磁盤轉動，但磁臂可以前后動，用于讀取不同磁道上的數據。磁道就是以盤片為中心劃分出來的一系列同心環(如圖標紅那圈)。磁道又劃分為一個個小段，叫扇區，是磁盤的最小存儲單元。

磁盤讀取時，系統將數據邏輯地址傳給磁盤，磁盤的控制電路會解析出物理地址，即哪個磁道哪個扇區。于是磁頭需要前后移動到對應的磁道，消耗的時間叫尋道時間，然后磁盤旋轉將對應的扇區轉到磁頭下，消耗的時間叫旋轉時間。所以，適當的操作順序和數據存放可以減少尋道時間和旋轉時間。
為了盡量減少I/O操作，磁盤讀取每次都會預讀，大小通常為頁的整數倍。即使只需要讀取一個字節，磁盤也會讀取一頁的數據(通常為4K)放入內存，內存與磁盤以頁為單位交換數據。因為局部性原理認為，通常一個數據被用到，其附近的數據也會立馬被用到。

B-Tree：如果一次檢索需要訪問4個節點，數據庫系統設計者利用磁盤預讀原理，把節點的大小設計為一個頁，那讀取一個節點只需要一次I/O操作，完成這次檢索操作，最多需要3次I/O(根節點常駐內存)。數據記錄越小，每個節點存放的數據就越多，樹的高度也就越小，I/O操作就少了，檢索效率也就上去了。

B+Tree：非葉子節點只存key，大大滴減少了非葉子節點的大小，那么每個節點就可以存放更多的記錄，樹更矮了，I/O操作更少了。所以B+Tree擁有更好的性能。

總結

以上是生活随笔為你收集整理的B+/-Tree原理及mysql的索引分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。