1. 首頁 > 生活百科 > >

4 MySQL學習---MySQL索引( 三 )

生活百科

  • 若根節點不是葉子節點，則至少有2個子節點
  • 所有的葉子結點都在同一層
  • 每個非葉子節點由n個鍵和n+1個指針組成，其中[ceil(m/2)-1]<=n<=m-1
    • B樹的主要特點如下：
    • B樹的節點中存儲著多個元素，每個內節點有多個分叉 。
    • 節點中的元素包含鍵值和數據，節點中的鍵值從大到小排列 。也就是說，所有的節點中都儲存數據 。
    • 父節點當中的元素不會出現在子節點中 。
    • 所有的葉子結點都位于同一層 ， 葉節點具有相同的深度，且彼此之間沒有指針連接 。
    B樹的簡圖如下圖所示：
    【4 MySQL學習---MySQL索引】
    4 MySQL學習---MySQL索引

    文章插圖
    注：這里限于篇幅，不再詳解B樹的插入和刪除操作，感興趣可到MySQL學習(5)---B樹和B+樹詳解查看 。
    應該說，B樹已經接近數據庫對底層數據結構的要求了 ， 但仍有可以優化的地方 。如：
    B樹不支持范圍查詢的快速查找，因為它采取了中序遍歷的方式 。以上圖為例，我們要查詢2~9之間的數據，在查找到2之后，需要回到根節點重新遍歷查找，需要從根節點進行多次遍歷，查詢效率有待提高 。
    如果data域中存儲的是行記錄，行的大小隨著列數的增多 ， 所占空間會變大 。這時，一個頁中可存儲的數據量就會變少，樹相應就會變高 ， 磁盤IO次數就會變大 。
    B+樹的引入B+樹，作為B樹的升級版，在B樹基礎上，MySQL在B樹的基礎上繼續改造，使用B+樹結構構建索引 。B+樹和B樹最主要的區別在于非葉子節點是否存儲數據的問題 。
    • B樹：非葉子節點（包括根節點）和葉子節點都會存儲數據 。
    • B+樹：只有葉子節點才會存儲數據，非葉子節點只存儲鍵值 。葉子節點之間使用雙向指針連接 ， 最底層的葉子節點形成了一個雙向有序鏈表 。
    B+樹的簡圖如下所示：
    4 MySQL學習---MySQL索引

    文章插圖
    B+樹的特征：
    • 有m個子節點的中間節點最多包含m個鍵（B樹中是m-1個鍵） ， 每個鍵不保存數據，只用來存儲索引 。
    • 所有的葉子結點中包含了全部關鍵字的信息，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序鏈接 。(而B樹的葉子節點并沒有包括全部需要查找的信息）
    B+樹的優勢：
    • 由于葉子節點上存放了所有的數據，并且有指針相連 ， 每個葉子節點在邏輯上是相連的，所以對于范圍查找比較友好 。
    • B+樹的所有數據都在葉子節點上，所以B+樹的查詢效率穩定，一般都是查詢3次 。
    • B+樹有利于磁盤的IO，因為他的層高基本不會因為數據擴大而增高 。（三層樹結構大概可以存放2000萬數據量）
    為什么說B+樹比B樹更適合數據庫索引？（1）B+樹的磁盤讀寫代價更低
    樹的內部結點并沒有指向關鍵字具體信息的指針 。因此其內部結點相對B樹更小 。如果把所有同一內部結點的關鍵字存放在同一磁盤塊中，那么磁盤塊所能容納的關鍵字數量也越多 。一次性讀入內存中的需要查找的關鍵字也就越多 。相對來說IO讀寫次數也就降低了 。
    （2）B+樹查詢效率更加穩定
    B樹搜索在非葉子節點還是葉子節點結束都有可能，越靠近根節點，查找效率越快；而B+樹無論查找的是什么數據，最終都需要從根節點一直走向葉節點，所有查找所經過的次數都是一樣的 ， 導致每一個數據的查詢效率相當 。
    （3）B+樹便于范圍查詢（最重要的原因 ， 范圍查找是數據庫的常態）
    B樹在提高了IO性能的同時并沒有解決元素遍歷效率低下的問題，正是為了解決這個問題，B+樹應用而生 。B+樹只需要去遍歷葉子節點就可以實現整棵樹的遍歷 。而且在數據庫中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作或者說效率太低 。
    補充：B樹的范圍查找采用中序遍歷，而B+樹采用在雙向鏈表上遍歷的方式 。
    索引分類可以查看官網文檔，看看MySQL存儲引擎支持的索引類型 。官網文檔：https://dev.mysql.com/doc/refman/8.0/en/create-index.html
    下圖是MySQLinnoDB、MYISAM、MEMORY、RDB存儲引擎對各種索引類型的支持情況 。

    由于本文是基于MySQL的innoDB存儲引擎，所以重點觀察第一個表格 。
    由于本文是基于MySQL的InnoDB存儲引擎，因此重點觀察第一個表格 ， 其他的表格可以自行觀看 。從表格中可以看出 ， InnoDB存儲引擎索引只支持BTREE類型的索引，索引的類別有Primary Key，Unique，Key ， FULLTEXT和SPATIAL 。

    推薦閱讀