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

MySQL的索引系統(tǒng)采用B+樹的原因解析

 更新時(shí)間:2021年09月09日 10:33:38   作者:微滑低  
索引是為了加速對表中數(shù)據(jù)行的檢索而創(chuàng)建的一種分散的存儲(chǔ)結(jié)構(gòu),這篇文章主要介紹了MySQL的索引系統(tǒng)采用B+樹的原因解析,需要的朋友可以參考下

1.什么是索引?

索引是為了加速對表中數(shù)據(jù)行的檢索而創(chuàng)建的一種分散的存儲(chǔ)結(jié)構(gòu)。(就好像我們小時(shí)候用的字典,有了字典查到對應(yīng)的字就會(huì)變快)

2.為什么需要索引?

首先我們需要了解一些概念和知識(shí)

  1. mysql數(shù)據(jù)存儲(chǔ)在什么地方?----磁盤
  2. 查詢數(shù)據(jù)比較慢的,一般情況下是卡在哪了? ----IO
  3. (所以我們要提高IO的效率,那么如何提高呢?---- 次數(shù)和量兩個(gè)層面,例如:搬磚,搬一次和搬十次耗費(fèi)的力氣是不一樣的,一次搬一塊和一次搬十塊耗費(fèi)的力氣(占用IO資源)也是不一樣的。所以我們盡可能的在滿足自身需求的前提下,減少和IO的交互)
  4. 去磁盤讀取數(shù)據(jù)的時(shí)候,是用多少讀取多少嘛? ----磁盤預(yù)讀
  5. 磁盤預(yù)讀:內(nèi)存跟磁盤在發(fā)生數(shù)據(jù)交互的時(shí)候,一般情況下有一個(gè)最小的邏輯單元,稱為頁,datapage,頁一般由操作系統(tǒng)決定是多大,一般是4k和8k,而我們在進(jìn)行數(shù)據(jù)交互的時(shí)候,可以取頁的的整數(shù)倍來進(jìn)行讀取,innodb存儲(chǔ)引擎每次讀取數(shù)據(jù)為16k
  6. 局部性原理:數(shù)據(jù)和程序都有聚集成群的傾向,同時(shí)之前被訪問過的數(shù)據(jù)和可能再次被查詢,涉及空間局部性、時(shí)間局部性

通過以上幾個(gè)概念我們大概知道索引是用來干嘛的了----預(yù)先設(shè)計(jì)好索引系統(tǒng),等我們查詢數(shù)據(jù)的時(shí)候,減少和IO的交互來提高我們的查詢效率。

3.如何設(shè)計(jì)索引系統(tǒng)?

我們還是先明白幾個(gè)概念

  • 索引存儲(chǔ)在哪?---- 磁盤,查詢數(shù)據(jù)的時(shí)候會(huì)優(yōu)先將索引加載到內(nèi)存中
  • 索引在存儲(chǔ)的時(shí)候需要什么信息?需要存什么字段值?

—— key:實(shí)際數(shù)據(jù)行中儲(chǔ)存的值
—— 文件地址(指針、我們需要找到存儲(chǔ)數(shù)據(jù)文件在哪就得靠文件地址)
—— offset:偏移量(如果我們要取文件中的某一條數(shù)據(jù)時(shí),就需要用到偏移量)

  • 上面說的這種格式的數(shù)據(jù)要使用什么樣的數(shù)據(jù)結(jié)構(gòu)來儲(chǔ)存?

—— 上面可知我們我們的數(shù)據(jù)格式是 K-V類型的
知道K-V格式數(shù)據(jù)那我們就知道使用什么數(shù)據(jù)結(jié)構(gòu)來儲(chǔ)存了,有哈希表、樹(二叉樹、二分查找樹、二分平衡樹、紅黑樹、B樹、B+樹
綜上所述,我們可以上面的數(shù)據(jù)結(jié)構(gòu)來設(shè)計(jì)我們的索引系統(tǒng)

4.MYSQL索引系統(tǒng)是什么呢?

為什么不按照上面說的格式儲(chǔ)存呢?

眾所周知,mysql的索引系統(tǒng)使用的是B+樹,為什么是B+樹呢?接下來我們逐個(gè)分析其他的存儲(chǔ)結(jié)構(gòu)為什么不行。在此之前,我們還是需要了解兩個(gè)前置知識(shí)----OLAP和OLTP

當(dāng)我們存儲(chǔ)的數(shù)據(jù)量越多時(shí),對應(yīng)建立的索引也會(huì)越大,當(dāng)我們從磁盤讀取到內(nèi)存時(shí)就會(huì)產(chǎn)生IO問題,那我們又對索引建立索引嘛?不是的,所以mysql采取的B+樹

5.哈希表

在這里插入圖片描述

上面是哈希表的存儲(chǔ)結(jié)構(gòu),我們來探討這類的存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)
缺點(diǎn):

  • 哈希沖突會(huì)造成數(shù)據(jù)散列不均勻,會(huì)產(chǎn)生大量的線性查詢,比較浪費(fèi)時(shí)間
  • 不支持范圍查詢,當(dāng)進(jìn)行范圍查詢的時(shí)候,必須要挨個(gè)遍歷
  • 對于內(nèi)存空間的要求比較高(要把全部數(shù)據(jù)加到到內(nèi)存中)

優(yōu)點(diǎn):
如果是等值查詢,那么會(huì)非常快

那么在mysql中有沒有hash索引呢?

  • memory存儲(chǔ)引擎使用的是hash索引
  • innodb支持自適應(yīng)hash

 6.樹

6.1 二叉樹

在這里插入圖片描述

二叉樹本身是無序的,當(dāng)我們在進(jìn)行數(shù)據(jù)查找時(shí)要挨個(gè)去跟每個(gè)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)對比,看是否符合我們的數(shù)據(jù)要求,效率低下

6.2 二分查找樹(Binary Search Tree ,BST)

在這里插入圖片描述

二分查找樹的特點(diǎn):插入數(shù)據(jù)的時(shí)候必須有序,左子樹必須小于跟節(jié)點(diǎn),右子樹必須保證大于根節(jié)點(diǎn)。所以使用二分查找樹對比二叉樹來顯然提高了查詢效率。
但是如果數(shù)據(jù)插入是遞增或者遞減的順序的話,二分查找樹就會(huì)退化成鏈表,查找效率又降低了

在這里插入圖片描述

6.3 平衡二叉樹(Balanced Binary Tree, AVL樹)

在這里插入圖片描述

根據(jù)二叉查找樹的所暴露出的問題,我們通過使用AVL樹經(jīng)過左旋或者右旋讓樹平衡。但是為了保證平衡,在插入數(shù)據(jù)的時(shí)候必須要旋轉(zhuǎn),通過插入性能的損失來彌補(bǔ)查詢性能的提升。讀多寫少的情況還好,但是如果我讀寫請求一樣多,那就不合適了。

6.4 紅黑樹

在這里插入圖片描述

紅黑樹也是經(jīng)過左旋和右旋讓樹平衡起來,還有變色的行為,最長子樹只要不超過最短子樹的兩倍即可…所以就能讓查詢性能和插入性能近似取得一個(gè)平衡,但是隨著數(shù)據(jù)的插入,發(fā)現(xiàn)樹的深度會(huì)變深,深的深度越深,意味著IO次數(shù)越多,影響數(shù)據(jù)讀取的效率。

6.5 B樹

針對紅黑樹暴露的問題,那么我們應(yīng)該如何提高讀取的效率呢?我們能不能從有序的二叉樹,變成有序的多叉樹呢,這樣我們就可以儲(chǔ)存更多的數(shù)據(jù)

在這里插入圖片描述

Degree為4表示的是一個(gè)節(jié)點(diǎn)存儲(chǔ)三個(gè)數(shù)據(jù)值,超過就要變換。那么實(shí)際的數(shù)據(jù)是怎么存儲(chǔ)的呢?我們需要Key完整的數(shù)據(jù)行

在這里插入圖片描述

上圖是B樹實(shí)際存儲(chǔ)數(shù)據(jù)的圖,每個(gè)節(jié)點(diǎn)有三個(gè)元素key、指針數(shù)據(jù)。
查找實(shí)例,如果我想找28這個(gè)數(shù)據(jù),先從磁盤塊1開始發(fā)現(xiàn)讀取不到,經(jīng)對比范圍在p2指針指向的磁盤塊3,還是沒找到,再根據(jù)磁盤塊3的p2指針指向磁盤塊8找到28。我們來分析一下,每個(gè)磁盤塊大小為16kb,我們查找了三個(gè)磁盤塊只需讀取48kb,那么三層B樹能存儲(chǔ)多少條記錄呢?

我們理想化一下,假設(shè)key和指針不占用大小,一條數(shù)據(jù)占用1k的大小,那么磁盤1數(shù)據(jù)可以存儲(chǔ)16條,磁盤3也是16條,磁盤8也是16條,那么我們只能存儲(chǔ)161616=4096條記錄,這明顯有點(diǎn)少了,而且我們是理想化的,實(shí)際key和指針也是占用大小的。

于是乎我們不禁思考,為什么存儲(chǔ)的數(shù)據(jù)量那么少?
我們發(fā)現(xiàn)每層存儲(chǔ)的大小都被data給占用了,那么我們能不能只存儲(chǔ)key跟指針呢?為此就引出了B+樹

6.6 B+樹

在這里插入圖片描述

B樹到B+樹的演變:非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù),葉子節(jié)點(diǎn)才存儲(chǔ)數(shù)據(jù)

在這里插入圖片描述

上圖我們可以假設(shè)p1和28為一組占用10字節(jié)大小,那么第一層可以存儲(chǔ)16000/10=1600個(gè)這樣的大小,第二層也是1600,第三層data占用1kb,那就是16條,所以總的存儲(chǔ)1600160016=40960000(4096萬)條記錄

mysql索引結(jié)構(gòu)一般3~4層,但是還要注意一個(gè)問題。假設(shè)我們就是3層存儲(chǔ)結(jié)構(gòu),如何存儲(chǔ)更多的數(shù)據(jù)?
剛剛我們假設(shè)的是p1和28為10字節(jié)大小,那如果它們是1字節(jié)呢,那么存儲(chǔ)總量是160001600010=4096000000。所以就引申出面試一直被提到的建立索引用int還是var好?

答:保證key的長度越小也好,varchar小于4字節(jié)用varcahr,大于4字節(jié)用int

根據(jù)B+樹的特點(diǎn),存儲(chǔ)量大,查詢快,所以mysql使用的就是B+樹

總結(jié)

至此mysql索引系統(tǒng)為什么使用的是B+樹就講述完了,如果有什么講錯(cuò)的地方希望能提醒我改正過來。

到此這篇關(guān)于MySQL的索引系統(tǒng)采用B+樹的原因解析的文章就介紹到這了,更多相關(guān)MySQL索引B+樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • MySQL查詢條件中in會(huì)用到索引嗎

    MySQL查詢條件中in會(huì)用到索引嗎

    這篇文章主要給大家介紹了MySQL查詢條件中in會(huì)不會(huì)用到索引的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用MySQL具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-07-07
  • MySQL之多表查詢自連接方式

    MySQL之多表查詢自連接方式

    這篇文章主要介紹了MySQL之多表查詢自連接方式,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2024-09-09
  • Win7、WinXP下MySql安裝出錯(cuò)完全卸載的方法步驟

    Win7、WinXP下MySql安裝出錯(cuò)完全卸載的方法步驟

    這篇文章主要介紹了Win7、WinXP下MySql安裝出錯(cuò)完全卸載的方法步驟,本文給出詳細(xì)的操作步驟,按本文方法清理后,重新安裝,應(yīng)該就不會(huì)有錯(cuò)誤了,需要的朋友可以參考下
    2015-06-06
  • MySQL 行轉(zhuǎn)列詳情

    MySQL 行轉(zhuǎn)列詳情

    這篇文章主要介紹了MySQL 行轉(zhuǎn)列詳情,MySQL 行轉(zhuǎn)列語句不難,具體的詳細(xì)資料,感興趣的小伙伴可以參考一下
    2022-01-01
  • MYSQL初學(xué)者命令行使用指南

    MYSQL初學(xué)者命令行使用指南

    其實(shí)MYSQL的對數(shù)據(jù)庫的操作與其它的SQL類數(shù)據(jù)庫大同小異,您最好找本將SQL的書看看。我在這里只介紹一些基本的,其實(shí)我也就只懂這些了,呵呵。最好的MYSQL教程還是“晏子“譯的“MYSQL中文參考手冊“不僅免費(fèi)每個(gè)相關(guān)網(wǎng)站都有下載,而且它是最權(quán)威的。
    2008-06-06
  • mysql創(chuàng)建外鍵報(bào)錯(cuò)的原因及解決(can't?not?create?table)

    mysql創(chuàng)建外鍵報(bào)錯(cuò)的原因及解決(can't?not?create?table)

    這篇文章主要介紹了mysql創(chuàng)建外鍵報(bào)錯(cuò)的原因及解決方案(can't?not?create?table),具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-09-09
  • 去掉mysql連接時(shí)報(bào)警聲音的方法

    去掉mysql連接時(shí)報(bào)警聲音的方法

    這篇文章主要介紹了去掉mysql連接時(shí)報(bào)警聲音的方法,本文直接給出設(shè)置命令和參數(shù),其中起作用的就是1個(gè)-p參數(shù),需要的朋友可以參考下
    2015-01-01
  • Ubuntu 18.04下mysql 8.0 安裝配置方法圖文教程

    Ubuntu 18.04下mysql 8.0 安裝配置方法圖文教程

    這篇文章主要為大家詳細(xì)介紹了Ubuntu 18.04下mysql 8.0 安裝配置方法圖文教程,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-05-05
  • 一文徹底搞清楚MySQL的主鍵、外鍵、約束和各種索引

    一文徹底搞清楚MySQL的主鍵、外鍵、約束和各種索引

    主鍵用于唯一標(biāo)識(shí)表中每一行數(shù)據(jù),外鍵用于建立表與表之間關(guān)聯(lián)關(guān)系,約束用于限制表中數(shù)據(jù)的規(guī)則,索引用于加速查詢,本文就將帶大家底搞清楚MySQL的主鍵、外鍵、約束和各種索引,感興趣的小伙伴可以跟著小編一起來學(xué)習(xí)
    2023-06-06
  • MySQL中獲取最大值MAX()函數(shù)和ORDER BY … LIMIT 1比較

    MySQL中獲取最大值MAX()函數(shù)和ORDER BY … LIMIT 1比較

    mysql取最大值的的是max 和order by兩種方式,同時(shí)也大多數(shù)人人為max的效率更高,在本文中,我們將介紹MySQL中MAX()和ORDER BY … LIMIT 1兩種獲取最大值的方法以及它們性能上的差異,同時(shí)我們將探討這種性能差異的原因,并提供一些優(yōu)化建議
    2024-03-03

最新評(píng)論