在mysql中使用B+樹索引的優勢有哪些?很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細講解,有這方面需求的人可以來學習下,希望你能有所收獲。
MySQL的存儲結構
單位:表>段>區>頁>行
在數據庫中, 不論讀一行,還是讀多行,都是將這些行所在的頁進行加載。也就是說存儲空間的基本單位是頁。
一個頁就是一棵樹B+樹的節點,數據庫I/O操作的最小單位是頁,與數據庫相關的內容都會存儲在頁的結構里。
在一棵B+樹中,每個節點為都是一個頁,每次新建節點的時候,就會申請一個頁空間
同一層的節點為之間,通過頁的結構構成了一個雙向鏈表
非葉子節點為,包括了多個索引行,每個索引行里存儲索引鍵和指向下一層頁面的指針
葉子節點為,存儲了關鍵字和行記錄,在節點內部(也就是頁結構的內部)記錄之間是一個單向的鏈表
有以下幾個特點
將所有的記錄分成幾個組, 每組會存儲多條記錄,
頁目錄存儲的是槽(slot),槽相當于分組記錄的索引,每個槽指針指向了不同組的最后一個記錄
我們通過槽定位到組,再查看組中的記錄
頁的主要作用是存儲記錄,在頁中記錄以單鏈表的形式進行存儲。
單鏈表優點是插入、刪除方便,缺點是檢索效率不高,最壞的情況要遍歷鏈表所有的節點。因此頁目錄中提供了二分查找的方式,來提高記錄的檢索效率。
我們再來看下B+樹的檢索過程
從B+樹的根開始,逐層找到葉子節點。
找到葉子節點為對應的數據頁,將數據葉加載到內存中,通過頁目錄的槽采用二分查找的方式先找到一個粗略的記錄分組。
在分組中通過鏈表遍歷的方式進行記錄的查找。
數據庫訪問數據要通過頁,一個頁就是一個B+樹節點,訪問一個節點相當于一次I/O操作,所以越快能找到節點,查找性能越好。
B+樹的特點就是夠矮夠胖,能有效地減少訪問節點次數從而提高性能。
下面,我們來對比一個二叉樹、多叉樹、B樹和B+樹。
二叉樹是一種二分查找樹,有很好的查找性能,相當于二分查找。
但是當N比較大的時候,樹的深度比較高。數據查詢的時間主要依賴于磁盤IO的次數,二叉樹深度越大,查找的次數越多,性能越差。
最壞的情況是退化成了鏈表,如下圖
為了讓二叉樹不至于退化成鏈表,人們發明了AVL樹(平衡二叉搜索樹):任何結點的左子樹和右子樹高度最多相差1
多叉樹就是節點可以是M個,能有效地減少高度,高度變小后,節點變少I/O自然少,性能比二叉樹好了
B樹簡單地說就是多叉樹,每個葉子會存儲數據,和指向下一個節點的指針。
例如要查找9,步驟如下
我們與根節點的關鍵字 (17,35)進行比較,9 小于 17 那么得到指針 P1;
按照指針 P1 找到磁盤塊 2,關鍵字為(8,12),因為 9 在 8 和 12 之間,所以我們得到指針 P2;
按照指針 P2 找到磁盤塊 6,關鍵字為(9,10),然后我們找到了關鍵字 9。
B+樹是B樹的改進,簡單地說是:只有葉子節點才存數據,非葉子節點是存儲的指針;所有葉子節點構成一個有序鏈表
B+樹的內部節點并沒有指向關鍵字具體信息的指針,因此其內部節點相對B樹更小,如果把所有同一內部節點的關鍵字存放在同一盤塊中,那么盤塊所能容納的關鍵字數量也越多,一次性讀入內存的需要查找的關鍵字也就越多,相對IO讀寫次數就降低了
例如要查找關鍵字16,步驟如下
與根節點的關鍵字 (1,18,35) 進行比較,16 在 1 和 18 之間,得到指針 P1(指向磁盤塊 2)
找到磁盤塊 2,關鍵字為(1,8,14),因為 16 大于 14,所以得到指針 P3(指向磁盤塊 7)
找到磁盤塊 7,關鍵字為(14,16,17),然后我們找到了關鍵字 16,所以可以找到關鍵字 16 所對應的數據。
B+樹與B樹的不同:
B+樹非葉子節點不存在數據只存索引,B樹非葉子節點存儲數據
B+樹查詢效率更高。B+樹使用雙向鏈表串連所有葉子節點,區間查詢效率更高(因為所有數據都在B+樹的葉子節點,掃描數據庫 只需掃一遍葉子結點就行了),但是B樹則需要通過中序遍歷才能完成查詢范圍的查找。
B+樹查詢效率更穩定。B+樹每次都必須查詢到葉子節點才能找到數據,而B樹查詢的數據可能不在葉子節點,也可能在,這樣就會造成查詢的效率的不穩定
B+樹的磁盤讀寫代價更小。B+樹的內部節點并沒有指向關鍵字具體信息的指針,因此其內部節點相對B樹更小,通常B+樹矮更胖,高度小查詢產生的I/O更少。
看完上述內容是否對您有幫助呢?如果還想對相關知識有進一步的了解或閱讀更多相關文章,請關注億速云行業資訊頻道,感謝您對億速云的支持。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。