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

一文了解mysql索引的數(shù)據(jù)結(jié)構(gòu)為什么要用B+樹

 更新時(shí)間:2022年04月25日 14:32:35   作者:YuShiwen?  
這篇文章主要介紹了一文了解mysql索引的數(shù)據(jù)結(jié)構(gòu)為什么用B+樹,在節(jié)點(diǎn)中存儲(chǔ)某段數(shù)據(jù)的首地址,并且B+樹的葉子節(jié)點(diǎn)用了一個(gè)鏈表串聯(lián)起來,便于范圍查找,下文利用各種索引的數(shù)據(jù)結(jié)構(gòu)的方法與B+樹做對(duì)比,看看它的優(yōu)勢到底是什么,感興趣的小伙伴可以參考一下

前提: 以下的一些數(shù)據(jù)結(jié)構(gòu)大家需提前知道,否則看起來會(huì)比較有困難,大家也可以按照本文所提到的知識(shí)點(diǎn)去主動(dòng)查閱學(xué)習(xí)。

1. Hash表?No

因考慮到在數(shù)據(jù)檢索的過程中經(jīng)常會(huì)有范圍的查詢(如下),而hash表不能提供這種功能。

SELECT * FROM hero WHERE age>5 AND age<20;

使用哈希算法實(shí)現(xiàn)的索引雖然可以做到快速檢索數(shù)據(jù),但是沒辦法做數(shù)據(jù)高效范圍查找,因此哈希索引是不適合作為 Mysql 的底層索引的數(shù)據(jù)結(jié)構(gòu)。

2. 二叉查找樹(BST)?No

二叉查找樹(Binary Search Tree)雖然可以達(dá)到范圍搜索,但是在樹的插入過程中,如果插入的數(shù)據(jù)本來就是有順序的,那么就會(huì)形成一條鏈(如下),它的最壞情況是O(n)。 

3. 紅黑樹?No

紅黑樹雖然看似達(dá)到了平衡狀態(tài),但是也會(huì)有極端情況存在,和上述BST樹一樣,雖然不會(huì)成為鏈狀,但是紅黑樹會(huì)存在右傾的現(xiàn)象。 

在數(shù)據(jù)庫中的基本主鍵自增操作,主鍵一般都是數(shù)百萬數(shù)千萬的,如果紅黑樹存在這種問題,對(duì)于查找性能而言也是巨大的消耗,我們數(shù)據(jù)庫不可能忍受這種無意義的等待的。

4. 平衡二叉樹(AVL)?差那么二點(diǎn)意思

平衡二叉樹,英文翻譯為Balanced Binary Tree,為啥叫AVL呢? AVL 是大學(xué)教授G.M. Adelson-VelskyE.M. Landis 名稱的縮寫,他們提出的平衡二叉樹的概念,為了紀(jì)念他們,將平衡二叉樹稱為 AVL樹。

AVL樹本質(zhì)上是一顆二叉查找樹,但是它又具有以下特點(diǎn):

  • 它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1,
  • 左右兩個(gè)子樹也都是一棵平衡二叉樹。

它不存在紅黑樹這種右傾的現(xiàn)象,也具備數(shù)據(jù)高效范圍查找的能力,但是數(shù)據(jù)庫查詢數(shù)據(jù)的瓶頸在于磁盤的IO,樹節(jié)點(diǎn)在磁盤空間中存儲(chǔ)可能是不連續(xù)的,假設(shè)我們一次IO讀取一個(gè)樹的節(jié)點(diǎn),此次讀入內(nèi)存的這頁中沒有其他樹的節(jié)點(diǎn),那么每讀取一個(gè)樹的節(jié)點(diǎn),就要進(jìn)行一次IO,這是多么消耗時(shí)間啊,所以我們設(shè)計(jì)數(shù)據(jù)庫索引時(shí)需要首先考慮怎么盡可能減少磁盤 IO 的次數(shù)。 磁盤讀取依靠的是機(jī)械運(yùn)動(dòng),分為尋道時(shí)間、旋轉(zhuǎn)延遲、傳輸時(shí)間三個(gè)部分,這三個(gè)部分耗時(shí)相加就是一次磁盤IO的時(shí)間;這個(gè)花費(fèi)的時(shí)間成本是內(nèi)存訪問的十幾萬倍左右。 正是由于磁盤IO是非常昂貴的操作,所以計(jì)算機(jī)操作系統(tǒng)對(duì)此做了優(yōu)化:預(yù)讀;每一次IO時(shí),不僅僅把當(dāng)前磁盤地址的數(shù)據(jù)加載到內(nèi)存,同時(shí)也把相鄰數(shù)據(jù)也加載到內(nèi)存緩沖區(qū)中。因?yàn)榫植款A(yù)讀原理說明:當(dāng)訪問一個(gè)地址數(shù)據(jù)的時(shí)候,與其相鄰的數(shù)據(jù)很快也會(huì)被訪問到。每次磁盤IO讀取的數(shù)據(jù)我們稱之為一頁(page)。一頁的大小與操作系統(tǒng)有關(guān),一般為4k或者8k。這也就意味著讀取一頁內(nèi)數(shù)據(jù)的時(shí)候,實(shí)際上發(fā)生了一次磁盤IO。

相關(guān)術(shù)語解釋:

扇區(qū)(sector):

  • 磁盤上的每個(gè)磁道被等分成多個(gè)弧段,這個(gè)弧段便稱作扇區(qū)(sector)。
  • 扇區(qū)是磁盤物理層面的名稱,它是實(shí)際發(fā)生讀寫的最底層。

磁盤塊(IO Block):

  • 操作系統(tǒng)不與扇區(qū)直接進(jìn)行交互,因?yàn)橐话闱闆r下一個(gè)扇區(qū)是512byte,如果1T去用512byte進(jìn)行劃分,那劃分的地址空間太多了,為了讓操作系統(tǒng)能夠?qū)ぶ返礁蟮牡刂房臻g,操作系統(tǒng)將相鄰的扇區(qū)組合在一起,形成一個(gè)塊,對(duì)塊進(jìn)行管理。每個(gè)磁盤塊可以包括 2、4、8、16、32 或 64 個(gè)扇區(qū),這便是磁盤塊(IO Block)。
  • 磁盤塊是操作系統(tǒng)中出現(xiàn)的名稱,文件系統(tǒng)讀寫數(shù)據(jù)的最小單位,它同時(shí)也被叫做磁盤簇。

頁(page):

  • 頁是內(nèi)存中出現(xiàn)的名稱,它是內(nèi)存的最小存儲(chǔ)單位,頁的大小通常為磁盤塊大小的 2^n 倍。

5. B-tree(B-樹也稱B樹)?差那么一點(diǎn)意思

B樹是一種平衡的多叉樹,B樹相比于平衡二叉樹(AVL),它能夠在單個(gè)節(jié)點(diǎn)中存儲(chǔ)大量鍵,也降低了樹的高度,從而減少了IO的次數(shù)。 

B樹的節(jié)點(diǎn)中存儲(chǔ)的是數(shù)據(jù),單個(gè)節(jié)點(diǎn)存儲(chǔ)的內(nèi)容還是太少了,如何讓一個(gè)節(jié)點(diǎn)存儲(chǔ)的內(nèi)容更多呢?B+樹它來了。

6. B+樹

在節(jié)點(diǎn)中存儲(chǔ)某段數(shù)據(jù)的首地址,并且B+樹的葉子節(jié)點(diǎn)用了一個(gè)鏈表串聯(lián)起來,便于范圍查找。 

B+樹高度降低,減少了磁盤 IO。其次,B+樹的葉子節(jié)點(diǎn)是真正數(shù)據(jù)存儲(chǔ)的地方,葉子節(jié)點(diǎn)用了鏈表連接起來,這個(gè)鏈表本身就是有序的,在數(shù)據(jù)范圍查找時(shí),更具備效率。因此 Mysql 的索引用的就是 B+樹,B+樹在查找效率、范圍查找中都有著非常不錯(cuò)的性能。

到此這篇關(guān)于一文了解mysql索引的數(shù)據(jù)結(jié)構(gòu)為什么用B+樹的文章就介紹到這了,更多相關(guān)mysql B+樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • MySQL進(jìn)行g(shù)roup by字段返回大量異常結(jié)果的問題解決

    MySQL進(jìn)行g(shù)roup by字段返回大量異常結(jié)果的問題解決

    本文主要介紹了MySQL進(jìn)行g(shù)roup by字段返回大量異常結(jié)果的問題解決,文中通過代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2024-05-05
  • 設(shè)置mysql5.7編碼集為utf8mb4的方法

    設(shè)置mysql5.7編碼集為utf8mb4的方法

    移動(dòng)端的表情或者一些emoji是4字節(jié)的,但是utf-8是3字節(jié)的,這篇文章主要介紹了設(shè)置mysql5.7編碼集為utf8mb4的方法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-11-11
  • MySQL中臨時(shí)表的使用示例

    MySQL中臨時(shí)表的使用示例

    這篇文章主要介紹了MySQL中的內(nèi)存臨時(shí)表的相關(guān)資料,幫助大家更好的理解和學(xué)習(xí)MySQL,感興趣的朋友可以了解下
    2020-11-11
  • docker下mysql 8.0.20 安裝配置方法圖文教程

    docker下mysql 8.0.20 安裝配置方法圖文教程

    這篇文章主要介紹了docker下mysql 8.0.20 安裝配置方法圖文教程,文中安裝步驟介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-05-05
  • MySQL數(shù)據(jù)庫卸載的完整步驟

    MySQL數(shù)據(jù)庫卸載的完整步驟

    這篇文章主要為大家詳細(xì)介紹了MySQL數(shù)據(jù)庫卸載的完整步驟,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-05-05
  • mysql重復(fù)索引與冗余索引實(shí)例分析

    mysql重復(fù)索引與冗余索引實(shí)例分析

    這篇文章主要介紹了mysql重復(fù)索引與冗余索引,簡單說明了重復(fù)索引與冗余索引的概念、應(yīng)用場景并結(jié)合實(shí)例形式分析了mysql重復(fù)索引與冗余索引相關(guān)操作技巧,需要的朋友可以參考下
    2019-07-07
  • mysql把主鍵定義為自動(dòng)增長標(biāo)識(shí)符類型

    mysql把主鍵定義為自動(dòng)增長標(biāo)識(shí)符類型

    這篇文章主要介紹了mysql中如何把主鍵定義為自動(dòng)增長標(biāo)識(shí)符類型,下面有個(gè)不錯(cuò)的示例,大家可以參考下
    2014-07-07
  • Mysql ERROR 1067: Invalid default value for字段問題

    Mysql ERROR 1067: Invalid default v

    這篇文章主要介紹了Mysql ERROR 1067: Invalid default value for字段問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-05-05
  • MySQL 8.0.18 Hash Join不支持left/right join左右連接問題

    MySQL 8.0.18 Hash Join不支持left/right join左右連接問題

    在MySQL 8.0.18中,增加了Hash Join新功能,它適用于未創(chuàng)建索引的字段,做等值關(guān)聯(lián)查詢。這篇文章給大家介紹MySQL 8.0.18 Hash Join不支持left/right join左右連接,感興趣的朋友一起看看吧
    2019-11-11
  • MLSQL編譯時(shí)權(quán)限控制示例詳解

    MLSQL編譯時(shí)權(quán)限控制示例詳解

    這篇文章主要給大家介紹了關(guān)于MLSQL編譯時(shí)權(quán)限控制的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用mysql具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-03-03

最新評(píng)論