欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

教你通過B+Tree平衡多叉樹理解InnoDB引擎的聚集和非聚集索引

 更新時間:2022年01月27日 15:56:26   作者:CaptainCats  
大家都知道B+Tree是從二叉樹演化而來,在這之前我們來先了解二叉樹、平衡二叉樹、平衡多叉樹,這篇文章主要介紹了通過B+Tree平衡多叉樹理解InnoDB引擎的聚集和非聚集索引,需要的朋友可以參考下

InnoDB引擎是通過B+Tree實現(xiàn)索引結構

因為B+Tree是從二叉樹演化而來,在這之前我們來先了解二叉樹、平衡二叉樹、平衡多叉樹。

二叉樹(Binary Tree)

簡介:每個節(jié)點最多有兩個子樹的樹結構。
它有一個特點:左子樹的鍵值小于根的鍵值,右子樹的鍵值大于根的鍵值。

如下圖(圖1)所示就是一個二叉樹:

在這里插入圖片描述

對于該二叉樹,假設我們要查找鍵值為5的節(jié)點:

首先從根節(jié)點開始,
第一次查找結果為6判斷5小于6;
往下查找6的左節(jié)點,結果為3判斷5大于3;
往下查找3的右節(jié)點,結果為5。
一共查找了3次。

我們可以發(fā)現(xiàn):

深度為1的節(jié)點需要查找一次,這樣的節(jié)點有1個需要查找1次;
深度為2的節(jié)點需要查找2次,這樣的節(jié)點有2個共需要查找4次;
深度為3的節(jié)點需要查找3次,這樣的節(jié)點有3個共需要查找9次。
如果要將所有節(jié)點全部查找遍歷一共需要查找1+4+9=14次。

二叉樹可以任意地構造,同樣是2、3、5、6、7、8這幾個數(shù)字,還可以按照下圖(圖2)的方式構造:

在這里插入圖片描述

如果要遍歷該二叉樹所有節(jié)點一共需要查找1+2+3+4+5+5=20次,這樣效率相對來說就比較低了。
若要最大程度地減少二叉樹的查找次數(shù),需要二叉樹盡可能地趨近于平衡二叉樹。

平衡二叉樹(AVL Tree)

簡介:在滿足二叉樹的前提下任一節(jié)點上左右兩個子樹的深度差不超過1。

下面兩個二叉樹,左邊的是平衡二叉樹,右邊的是非平衡二叉樹:

在這里插入圖片描述


 

如果在平衡二叉樹中插入或刪除節(jié)點,可能會導致平衡二叉樹失衡。
這種失去平衡的二叉樹可以概括為四種姿態(tài):LL(左左)、RR(右右)、LR(左右)、RL(右左)。

它們的示意圖如下:

在這里插入圖片描述

這四種失去平衡的姿態(tài)都有各自的定義:
LL:LeftLeft,也稱“左左”。
插入或刪除一個節(jié)點后,根節(jié)點的左孩子(Left Child)的左孩子(Left Child)還有非空節(jié)點,導致根節(jié)點的左子樹高度比右子樹高度高2,AVL樹失去平衡。
RR:RightRight,也稱“右右”。
插入或刪除一個節(jié)點后,根節(jié)點的右孩子(Right Child)的右孩子(Right Child)還有非空節(jié)點,導致根節(jié)點的右子樹高度比左子樹高度高2,AVL樹失去平衡。
LR:LeftRight,也稱“左右”。
插入或刪除一個節(jié)點后,根節(jié)點的左孩子(Left Child)的右孩子(Right Child)還有非空節(jié)點,導致根節(jié)點的左子樹高度比右子樹高度高2,AVL樹失去平衡。
RL:RightLeft,也稱“右左”。
插入或刪除一個節(jié)點后,根節(jié)點的右孩子(Right Child)的左孩子(Left Child)還有非空節(jié)點,導致根節(jié)點的右子樹高度比左子樹高度高2,AVL樹失去平衡。
平衡二叉樹失衡后,可以通過旋轉二叉樹使其恢復平衡。具體這四種失去平衡姿態(tài)情況下對應的旋轉方法,請移步BTree和B+Tree詳解,里面有十分詳細的講解,這里不再贅述。

平衡多叉樹(B-Tree)

B-Tree是為磁盤等設備設計的一種平衡查找樹,因此在講B-Tree之前先了解下磁盤的相關知識。

系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存時是以磁盤塊(block)為基本單位的,位于同一個磁盤塊中的數(shù)據(jù)會被一次性讀取出來,而不是需要什么取什么。

InnoDB存儲引擎中有頁(Page)的概念,頁是其磁盤管理的最小單位。InnoDB存儲引擎中默認每個頁的大小為16KB,可通過參數(shù)innodb_page_size將頁的大小設置為4K、8K、16K,
在MySQL中可通過如下命令查看頁的大?。?/p>

mysql> show variables like 'innodb_page_size';

而系統(tǒng)一個磁盤塊的存儲空間往往沒有這么大,因此InnoDB每次申請磁盤空間時都會是若干個地址連續(xù)磁盤塊(成為大磁盤塊即頁,接下來的部分如無特殊說明,所說磁盤塊即是InnoDB的頁)來達到頁的大小16KB。
InnoDB在把磁盤數(shù)據(jù)讀取到內(nèi)存時會以頁為基本單位。

B-Tree結構的數(shù)據(jù)可以讓系統(tǒng)高效的找到數(shù)據(jù)所在的磁盤塊。
為了描述B-Tree,首先定義一條記錄為一個對象[key, data],key為記錄的鍵值,對應表中的主鍵,data為一行記錄中除主鍵外的數(shù)據(jù)。對于不同的記錄,key值互不相同。

m(整數(shù))階(寬度為m,m>2)B-Tree滿足以下條件:

每個節(jié)點占用一個磁盤塊;
節(jié)點(除葉節(jié)點外)包含指針、鍵值(關鍵字)、數(shù)據(jù)三種元素,葉節(jié)點不包含其它節(jié)點的關鍵字信息:即指針;
所有葉子節(jié)點都在同一層;
節(jié)點擁有n個按照升序排序的不連續(xù)關鍵字,n在[m/2, m-1]閉區(qū)間內(nèi)為整數(shù);
除葉節(jié)點外,n個關鍵字劃分出n+1個范圍域?qū)猲+1個指針。指針指向子樹關鍵字的范圍域,
比如:以根節(jié)點為例,關鍵字為17和35,p1指針指向的子樹的數(shù)據(jù)范圍域小于17,p2指針指向的子樹的數(shù)據(jù)范圍域在(17, 35)開區(qū)間內(nèi),p3指針指向的子樹的數(shù)據(jù)范圍域大于35。

見下圖:
磁盤塊3也是包含三個指針,只是p1和p3的指向磁盤塊沒有畫出來。

在這里插入圖片描述

如果要查找關鍵字29,
那么首先會把磁盤塊1由磁盤加載到內(nèi)存,此時發(fā)生一次IO,
在內(nèi)存中用二分法查找確定29在17和35之間,鎖定磁盤塊1的P2指針,內(nèi)存時間因為非常短(相比磁盤的IO)可以忽略不計,
通過磁盤塊1的P2指針的磁盤地址把磁盤塊3由磁盤加載到內(nèi)存,發(fā)生第二次IO,
29在26和30之間,鎖定磁盤塊3的P2指針,
通過指針加載磁盤塊8到內(nèi)存,發(fā)生第三次IO,
同時內(nèi)存中做二分查找找到29,結束查詢,總計三次IO。


基礎·磁盤IO與預讀:
磁盤讀取依靠的是機械運動,分為尋道時間、旋轉延遲、傳輸時間三個部分,
這三個部分耗時相加就是一次磁盤IO的時間,大概9ms左右。這個成本是訪問內(nèi)存的十萬倍左右;
正是由于磁盤IO是非常昂貴的操作,所以計算機操作系統(tǒng)對此做了優(yōu)化:
預讀:每一次IO時,不僅僅把當前磁盤地址的數(shù)據(jù)加載到內(nèi)存,同時也把相鄰數(shù)據(jù)也加載到內(nèi)存緩沖區(qū)中。
因為局部預讀原理說明,當訪問一個地址數(shù)據(jù)的時候,與其相鄰的數(shù)據(jù)很快也會被訪問到。
每次磁盤IO讀取的數(shù)據(jù)我們稱之為一頁(page)。一頁的大小與操作系統(tǒng)有關,一般為4k或者8k。這也就意味著讀取一頁內(nèi)數(shù)據(jù)的時候,實際上發(fā)生了一次磁盤IO。

我們再來看二叉樹的查找過程

定義一個樹高為4的二叉樹,查找值為10:

在這里插入圖片描述

第一次磁盤IO:

在這里插入圖片描述

第二次磁盤IO:

在這里插入圖片描述

第三次磁盤IO:

在這里插入圖片描述

第四次磁盤IO:

在這里插入圖片描述

可以看到最壞情況下,磁盤的IO次數(shù)等于VAL樹的高度。

二叉樹深度和節(jié)點數(shù)的關系:

在這里插入圖片描述

相比VAL二叉樹,B-Tree可以大大減少磁盤IO次數(shù)。

B+Tree

B+tree是基于B-tree的變體。

B-Tree結構中每個節(jié)點中不僅包含數(shù)據(jù)的key值,還有data值,而每一個節(jié)點的存儲空間是有限的,
如果data數(shù)據(jù)比較大會導致每個節(jié)點能存儲的key的數(shù)量變少,導致數(shù)據(jù)量很大時B-Tree的深度較大,增大查詢時的磁盤I/O次數(shù),進而影響查詢效率。
在B+Tree中,所有數(shù)據(jù)記錄節(jié)點都存放在同一層的葉子節(jié)點上,而非葉子節(jié)點上只存儲key值信息,這樣可以大大加大每個節(jié)點存儲的key值數(shù)量,降低B+Tree的高度。

在這里插入圖片描述

和B-Tree不同,由于它的非葉子節(jié)點不存儲data信息,所以相同的鍵值會和data一起,出現(xiàn)在葉子節(jié)點中。
以磁盤塊3的p2指針為例,指針指向的子樹的數(shù)據(jù)范圍域就是在在[36, 79)左開右閉區(qū)間內(nèi)。

InnoDB存儲引擎中頁的大小為16KB,一般表的主鍵類型為INT(占用4個字節(jié))或BIGINT(占用8個字節(jié)),指針類型也一般為4或8個字節(jié),
一個頁(B+Tree中的一個節(jié)點)中大概能存儲16KB/(8B+8B)=1K個鍵值(為方便計算,這里的K取值為[10]^3)。
也就是說一個深度為3的B+Tree索引大概可以維護10^3 * 10^3 * 10^3 = 10億條記錄。

實際情況中每個節(jié)點可能不能填充滿,因此在數(shù)據(jù)庫中,B+Tree的高度一般都在2~4層。
mysql的InnoDB存儲引擎在設計時是將根節(jié)點常駐內(nèi)存的,也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作。

聚集和非聚集索引

到這兒,再來理解聚集和非聚集索引就比較簡單了。

聚集索引(clustered index)

通常,聚集索引是主鍵的同義詞。一個表中只能擁有一個聚集索引。
聚集索引的邏輯順序與數(shù)據(jù)庫表中記錄在磁盤上的排列順序一致。通俗來講就是,聚集索引葉子節(jié)點中存儲的數(shù)據(jù)包含表中一條記錄完整的信息。找到鍵值key就找到了整條數(shù)據(jù)。

非聚集索引(secondary index)

非聚集索引相對來說就不是那么好理解一點。
因為前面我們講到的關鍵值key對應的都是數(shù)據(jù)庫中唯一的一條記錄,而非聚集索引不一樣,它的關鍵值key無法確定唯一一條記錄,多條記錄的key值可能會相同。
非聚集索引是通過溢出頁來處理這種情況的,當多條記錄對應某個同一關鍵值key時,分配出一個溢出頁,
用來存放重復鍵值及其對應記錄的偏移量(該條記錄在磁盤上的實際物理位置)。和HashMap解決Hash key沖突類似。
非聚集索引維護了表中記錄的邏輯順序,但是它的葉子節(jié)點存儲的是表中的記錄在數(shù)據(jù)頁中的指針,相比聚集索引會多一次磁盤IO。

以上見解如有不當之處,請予指正。

參考文章
過來啊小蓮BTree和B+Tree詳解
lbcBoy索引原理-BTree講解

還有兩篇找不到了,找齊之后會在這里補上。

補充參考文章
SeedQiB-Tree詳解

到此這篇關于通過B+Tree平衡多叉樹理解InnoDB引擎的聚集和非聚集索引的文章就介紹到這了,更多相關B+Tree平衡多叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • Java數(shù)據(jù)結構之鏈表的概念及結構

    Java數(shù)據(jù)結構之鏈表的概念及結構

    這篇文章主要介紹了數(shù)據(jù)鏈表的概念及結構,鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構,數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。想進一步了解的同學,可以參考閱讀本文
    2023-04-04
  • SpringBoot如何實現(xiàn)starter原理詳解

    SpringBoot如何實現(xiàn)starter原理詳解

    這篇文章主要介紹了SpringBoot如何實現(xiàn)starter原理詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-06-06
  • Springboot日期轉換器實現(xiàn)代碼及示例

    Springboot日期轉換器實現(xiàn)代碼及示例

    這篇文章主要介紹了Springboot日期轉換器實現(xiàn)代碼及示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-08-08
  • Java流程控制之順序結構

    Java流程控制之順序結構

    Java中的流程控制語句可以這樣分類:順序結構,選擇結構,循環(huán)結構。下面文章我們就來看看來順序結構的詳細介紹,主要以順序結構簡單圖示及詳細解說該內(nèi)容,需要的小伙伴可以參考一下
    2021-12-12
  • Java基于PDFbox實現(xiàn)讀取處理PDF文件

    Java基于PDFbox實現(xiàn)讀取處理PDF文件

    PDFbox是一個開源的、基于Java的、支持PDF文檔生成的工具庫,它可以用于創(chuàng)建新的PDF文檔,修改現(xiàn)有的PDF文檔,還可以從PDF文檔中提取所需的內(nèi)容。本文將具體介紹一下PDFbox讀取處理PDF文件的示例代碼,感興趣的可以學習一下
    2022-02-02
  • 解析Jmeter脫離Jenkins后Ant集成郵件通知問題

    解析Jmeter脫離Jenkins后Ant集成郵件通知問題

    今天來講下本地的ant構建并發(fā)送郵件。配置下來挺順利也挺簡單的,對Jmeter脫離Jenkins后Ant集成郵件通知問題感興趣的朋友跟隨小編一起看看吧
    2021-12-12
  • Java實現(xiàn)把文件壓縮成zip文件的示例代碼

    Java實現(xiàn)把文件壓縮成zip文件的示例代碼

    這篇文章主要為大家介紹了如何通過Java語言實現(xiàn)將文件壓縮成zip文件,本文中示例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-02-02
  • java實現(xiàn)即時通信的完整步驟分享

    java實現(xiàn)即時通信的完整步驟分享

    這篇文章主要給大家介紹了關于java實現(xiàn)即時通信的完整步驟,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-09-09
  • Java實現(xiàn)文件上傳的兩種方法(uploadify和Spring)

    Java實現(xiàn)文件上傳的兩種方法(uploadify和Spring)

    這篇文章主要為大家詳細介紹了Java實現(xiàn)文件上傳的兩種方法,uploadify和Spring實現(xiàn)文件上傳,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-11-11
  • Java中的@builder建造者模式詳細解析

    Java中的@builder建造者模式詳細解析

    這篇文章主要介紹了Java中的@builder建造者模式詳細解析,使用 @Builder 注解可以簡化手動編寫建造者模式的代碼,使代碼更加簡潔易讀,它可以自動生成鏈式調(diào)用的方法來設置對象的屬性,并且可以在需要時進行可選屬性的設置,需要的朋友可以參考下
    2024-01-01

最新評論