【數據庫】B+樹與索引之間的恩怨情仇

midnight_time 2022-01-08 07:34:50 阅读数:890

b+ 索引 恩怨 情仇

前言

本文參考了圖靈學院線上直播課。

按照陳樹義前輩在《聊聊整體性學習方法》一文中提到的思想,本文思路如下:

  1. 獲取:什麼是B+樹、索引?
  2. 理解:B+樹的特點、索引的作用?
  3. 擴展:B+樹與B-樹、AVL樹、紅黑樹、二叉樹、Hash的區別?
  4. 糾錯:怎樣一眼區分B-樹與B+樹?
  5. 應用:如何更好的建錶、創建索引?

正文

一、什麼是B+樹、索引?

​ B+樹是一種數據結構,如下圖百度百科所說:

B+樹
​ 索引是一種有序的存儲結構,如下圖百度百科所說:

索引
​ 二者間關系就是,再Mysql數據庫中,常用B+樹的數據結構來存儲索引。

二、B+樹的特點、索引的作用?

​ B+樹的特點百度百科說是可以保持數據穩定有序,插入與修改擁有較穩定的時間複雜度

​ 索引的作用百度百科說是相當於圖書的目錄,可根據目錄中的頁碼快速找到所需的內容。

三、B+樹與B-樹、AVL樹、紅黑樹、二叉樹、Hash的區別?

​ 關於這些樹的區別可以參考文章《淺談AVL樹,紅黑樹,B樹,B+樹原理及應用》

​ 我憑我淺顯的理解,畫出了下面這個關系

二叉樹
上圖最下面的B+樹data之間其實是雙箭頭關系(老師說這裏他畫錯了),只有這樣才能實現區間查詢
其中一些名詞解釋:

AVL解釋:
an AVL tree (Georgy Adelson-Velsky and Landis’ tree, named after the inventors) is a self-balancing binary search tree.
AVL是按照其發明人的姓氏首字母命名的,原名是自動平衡二叉樹。

紅黑樹原名是symmetric binary B-trees 平衡二叉B樹

B-樹解釋:
a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children (Comer 1979, p. 123). Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.
B-樹與B+樹屬於多路平衡二叉樹

​ 上面都是一些樹之間的關系,另外還有一個東西叫Hash(哈希)

准確的說,Hash只是一個公式,即Hash函數。如下圖百度百科所述:
Hash

​ Hash錶與二叉樹結合看,如下圖:

Hash與二叉樹
​ 在Mysql創建索引時,可以選擇BTREE與HASH兩種索引方式。

​ 二者顯著的區別就是:BTREE支持等值查詢區間查詢而Hash只支持等值查詢。(注意:二者都不支持不等查詢,思考一下即可知道,無論BTREE還是HASH,都是通過指定值查詢的,對於 != 或 <> 查詢,只能進行全錶查詢

​ 可以發現,Hash錶無論數據有多少,只有一級,因此,查詢比BTREE快,但因其不支持區間查詢,而被大多數業務所舍弃。

​ 老師在課上還大概估算了一下3級B+樹大概能存多少數據,估算方法如下:

​ Mysql默認B+樹一層大小設置為16KB

​ 每層中會存儲索引地址(8B/個)和指向下級索引的指針(6B/個),共能存儲約 1170個索引節點

​ 1170個索引節點大概能指向16個1KB大小的數據文件(假設1條記錄1KB)

​ 最後估算得出,僅僅3層B+樹,大概能存儲數據量為 1170 * 1170 * 16 ≈ 2000W 條1KB的數據

2千萬計算

四、以前一些錯誤的思想

​ B-樹,讀音:B樹,- 只是個符號

​ 一眼區分B-樹與B+樹的方法:
B樹

B+樹

五、如何更好的建錶、創建索引?

​ 理論基礎已經搭好了,以後實戰之後再來補這塊…

​ 另外還有一些InnoDB與MyISAM存儲引擎的知識,可以參考知乎《Mysql 中 MyISAM 和 InnoDB 的區別有哪些?》

版权声明:本文为[midnight_time]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080734498524.html