mysql樹高怎么計(jì)算,mysql b+樹高度

Mysql InnoDB b+樹的高度

為什么Mysql考慮使用B+樹，而不是B樹，其實(shí)我們可以先了解下B樹和B+樹的特點(diǎn)來看下。

在永勝等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站 網(wǎng)站設(shè)計(jì)制作按需設(shè)計(jì),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),營銷型網(wǎng)站建設(shè),外貿(mào)營銷網(wǎng)站建設(shè),永勝網(wǎng)站建設(shè)費(fèi)用合理。

※ 樹的每個(gè)結(jié)點(diǎn)都會(huì)存儲(chǔ)數(shù)據(jù)

※ 單次查詢不一定要遍歷到樹的根部，平均查詢時(shí)間會(huì)比較快

※ 非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)（冗余）索引，索引包含主鍵和指針

※ 葉子節(jié)點(diǎn)才真正存儲(chǔ)數(shù)據(jù)

※ 每個(gè)葉子節(jié)點(diǎn)互相鏈表相連，保證了范圍查詢的時(shí)效性(頁之間用雙向鏈表連接，數(shù)據(jù)間用單項(xiàng)鏈表鏈接)

InnoDB最小存儲(chǔ)單位是頁，葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)最小單位都是頁，頁大小Mysql 默認(rèn)設(shè)定16384字節(jié)，約為16KB。

我們假設(shè)主鍵ID為bigint類型，長度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)，這樣一共14字節(jié)

我們一個(gè)頁中能存放多少這樣的索引元素，其實(shí)就代表有多少指針，即16384/14=1170;

高度為2的B+樹能存放1170×16=18720

高度為3的B+樹能存放1170×1170×16 = 21902400

InnoDB中B+樹高度一般為1-3層，它就能滿足千萬級(jí)的數(shù)據(jù)存儲(chǔ)。

在查找數(shù)據(jù)時(shí)一次頁的查找代表一次IO，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)。

MySQL_索引樹

查看樹插入刪除圖解：

時(shí)間復(fù)雜度：O(N)

時(shí)間復(fù)雜度：O(logn)

如果數(shù)據(jù)插入是遞增或者遞減順序的話，會(huì)使樹成為鏈?zhǔn)浇Y(jié)構(gòu)。 時(shí)間復(fù)雜度：O(N)

為了保證平衡，在插入或者刪除的時(shí)候必須要旋轉(zhuǎn)，通過插入或者刪除性能的損失來彌補(bǔ)查詢性能的提升。

但如果寫請(qǐng)求和讀請(qǐng)求一樣多的時(shí)候怎么辦？

隨著數(shù)據(jù)的插入，樹的深度會(huì)變深，樹的深度越深，意味著 IO 次數(shù)越多。影響數(shù)據(jù)讀取的效率。

MySQL 的頁大小是16k。假設(shè)只有data 占用空間且占用 1k 一個(gè)磁盤塊可以放置16條記錄，三層就是 4096條記錄。肯定小于 4096.

如果想要放入更多的數(shù)據(jù)的化，得加層。加層 IO 量肯定上來了。

data 太占內(nèi)存，導(dǎo)致存儲(chǔ)數(shù)據(jù)太少。

MySQL加載索引是以磁盤塊（頁）為單位的，頁（Page）是 Innodb 存儲(chǔ)引擎用于管理數(shù)據(jù)的最小磁盤單位。默認(rèn)的頁大小為 16KB。

假設(shè)只有 p1+key 值 占用空間且占用 10字節(jié)， 一個(gè)磁盤塊可以放置1600條記錄，三層就是 40960000條記錄。

在B+樹 上有兩個(gè)頭節(jié)點(diǎn)，一個(gè)指向根節(jié)點(diǎn)，另一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)，而且所有的葉子節(jié)點(diǎn)（即數(shù)據(jù)節(jié)點(diǎn)）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)，因此可以對(duì) B+樹 進(jìn)行兩種查找運(yùn)算：一種是對(duì)于主鍵的范圍查找和分頁查找，另一種是從根節(jié)點(diǎn)開始，進(jìn)行隨機(jī)查找。

讓當(dāng)前key值盡可能的少占用存儲(chǔ)空間，才能保證存儲(chǔ)更多的值。降低樹的高度，減少IO。

保證key的長度越小越好。

mysql innoDB中b+樹總結(jié)

B+樹在B樹的基礎(chǔ)上的一中優(yōu)化,InnoDB和MylSAM存儲(chǔ)引擎都是用B+樹實(shí)現(xiàn)索引結(jié)構(gòu)

B樹的索引和關(guān)鍵字key-data存儲(chǔ)在磁盤里面,然后被磁盤IO操作讀入內(nèi)存,如果這個(gè)data很大的話,每次加到內(nèi)存中的key就會(huì)減少, 這會(huì)使得B數(shù)的高度增加,這樣還是會(huì)增加磁盤IO查詢

為了解決這個(gè)問題, B+樹將所有數(shù)據(jù)記錄節(jié)點(diǎn)按照鍵值的大小順序存放在同一層葉子節(jié)點(diǎn)上, 而非葉子節(jié)點(diǎn)只存儲(chǔ)key值信息,這樣可以大大增加每個(gè)節(jié)點(diǎn)存儲(chǔ)的key值的數(shù)量,降低B+樹的高度

非葉子節(jié)點(diǎn)只存鍵值信息,所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針,數(shù)據(jù)記錄都存在葉子節(jié)點(diǎn)上如圖:

InnoDB存儲(chǔ)引擎最小的存儲(chǔ)單元是(頁), 每一頁的大小是16k(即16384個(gè)字節(jié)),每一行數(shù)據(jù)大概就是1k左右,那么一頁就可以存16條數(shù)據(jù)

那么在InnoDb中2層的高度的B+樹能存多少條數(shù)據(jù),我們來分析一下:

在InnoDB中每個(gè)指針為6個(gè)字節(jié),一個(gè)鍵值4-8個(gè)字節(jié)(如:Id為主鍵 - bigInt類型是8字節(jié))那么加起來就是14個(gè)字節(jié), 那么一頁就能存16384 / 14 =1170個(gè)指針, 所以2層的B+樹能存1170*16=18720條數(shù)據(jù)

在InnoDB在B+樹高度一般為3層所以1170 * 1170 * 16= 21902400 條數(shù)據(jù),能存千萬級(jí)別的數(shù)據(jù)

MySQL——關(guān)于索引的總結(jié)

首先說說索引的 優(yōu)點(diǎn) ：最大的好處無疑就是提高查詢效率。有的索引還能保證數(shù)據(jù)的唯一性，比如唯一索引。

而它的 壞處 也很明顯：索引也是文件，我們在創(chuàng)建索引時(shí)，也會(huì)創(chuàng)建額外的文件，所以會(huì)占用一些硬盤空間。其次，索引也需要維護(hù)，我們在增加刪除數(shù)據(jù)的時(shí)候，索引也需要去變化維護(hù)。當(dāng)一個(gè)表的索引多了以后，資源消耗是很大的，所以必須結(jié)合實(shí)際業(yè)務(wù)再去確定給哪些列加索引。

再說說索引的基本結(jié)構(gòu)。一說到這里肯定會(huì)脫口而出：B+樹！了解B+樹前先要了解二叉查找樹和二叉平衡樹。 二叉查找樹 ：左節(jié)點(diǎn)比父節(jié)點(diǎn)小，右節(jié)點(diǎn)比父節(jié)點(diǎn)大，所以二叉查找樹的中序遍歷就是樹的各個(gè)節(jié)點(diǎn)從小到大的排序。 二叉平衡樹 ：左右子樹高度差不能大于1。B+樹就是結(jié)合了它們的特點(diǎn)，當(dāng)然，不一定是二叉樹。

為什么要有二叉查找樹的特點(diǎn)？？ 因?yàn)椴檎倚士欤植檎以谶@種結(jié)構(gòu)下，查找效率是很快的。 那為什么要有平衡樹的特點(diǎn)呢？ 試想，如果不維護(hù)一顆樹的平衡性，當(dāng)插入一些數(shù)據(jù)后，樹的形態(tài)有可能變得很極端，比如左子樹一個(gè)數(shù)據(jù)沒有，而全在右子樹上，這種情況下，二分查找和遍歷有什么區(qū)別呢？而就是因?yàn)檫@些特點(diǎn)需要去維護(hù)，所以就有了上面提到的缺點(diǎn)，當(dāng)索引很多后，反而增加了系統(tǒng)的負(fù)擔(dān)。

接著說B+樹。 它的結(jié)構(gòu)如下 ：

可以發(fā)現(xiàn)，葉子節(jié)點(diǎn)其實(shí)是一個(gè) 雙向循環(huán)鏈表 ，這種結(jié)構(gòu)的好處就是，在范圍查詢的時(shí)候，我只用找到一個(gè)數(shù)據(jù)，就可以直接返回剩余的數(shù)據(jù)了。比如找小于30的，只用找到30，其余的直接通過葉子節(jié)點(diǎn)間的指針就可以找到。再說說其他特點(diǎn)： 數(shù)據(jù)只存在于葉子節(jié)點(diǎn) 。當(dāng)葉子節(jié)點(diǎn)滿了，如果再添加數(shù)據(jù)，就會(huì)拆分葉子節(jié)點(diǎn)，父節(jié)點(diǎn)就多了個(gè)子節(jié)點(diǎn)。如果父節(jié)點(diǎn)的位置也滿了，就會(huì)擴(kuò)充高度，就是拆分父節(jié)點(diǎn)，如25 50 75拆分成：25為左子樹，75為右子樹，50變成新的頭節(jié)點(diǎn)，此時(shí)B+樹的高度變成了3。它們的擴(kuò)充的規(guī)律如下表，Leaf Page是葉子節(jié)點(diǎn)，index Page是非葉子節(jié)點(diǎn)。

再說說B樹 ，B樹相比較B+樹，它所有節(jié)點(diǎn)都存放數(shù)據(jù)，所以在查找數(shù)據(jù)時(shí)，B樹有可能沒到達(dá)葉子節(jié)點(diǎn)就結(jié)束了。再者，B樹的葉子節(jié)點(diǎn)間不存在指針。

最后說說Hash索引 ，相較于B+樹，Hash索引最大的優(yōu)點(diǎn)就是查找數(shù)據(jù)快。但是Hash索引最大的問題就是不支持范圍查詢。試想，如果查詢小于30的數(shù)據(jù)，hash函數(shù)是根據(jù)數(shù)據(jù)的值找到其對(duì)應(yīng)的位置，誰又知道小于30的有哪幾個(gè)數(shù)據(jù)。而B+樹正好相反，范圍查詢是它的強(qiáng)項(xiàng)。

附錄： Hash到底是啥？？ 哈希中文名散列，哈希只是它的音譯。 為啥都說Hash快？？ 首先有一塊哈希表（散列表），它的數(shù)據(jù)結(jié)構(gòu)是個(gè)數(shù)組，一個(gè)任意長度的數(shù)據(jù)通過hash函數(shù)都可以變成一個(gè)固定長度的數(shù)據(jù)，叫hash值。然后通過hash值確定在數(shù)組中的位置，相同數(shù)據(jù)的hash值是相同的，所以我們存儲(chǔ)一個(gè)數(shù)據(jù)以后，只需O(1)的時(shí)間復(fù)雜度就可以找到數(shù)據(jù)。 那hash函數(shù)又是啥？？ 算術(shù)運(yùn)算或位運(yùn)算，很多應(yīng)用里都有hash函數(shù)，但實(shí)際運(yùn)算過程大不一樣。這是Java里String的hashCode方法：

publicint hashCode() {

}

還有一個(gè)問題，hash函數(shù)計(jì)算出來的hash值有可能存在碰撞，即兩個(gè)不同的數(shù)據(jù)可能存在相同的hash值，在MySQL或其他的應(yīng)用中，如Java的HashMap等，如果存在碰撞就會(huì)以當(dāng)前數(shù)組位置為頭節(jié)點(diǎn)，轉(zhuǎn)變成一個(gè)鏈表。

說到這里也清楚了為啥Java中引用類型要同時(shí)重寫hashCode和equals了。兩個(gè)對(duì)象，實(shí)例就算一模一樣，它們的hash值也不相等， 為啥不相等？？ 默認(rèn)的Object的hashCode方法會(huì)根據(jù)對(duì)象來計(jì)算hash值的，實(shí)例相同，但它們還是兩個(gè)不同的對(duì)象啊，所以我們重寫hashCode時(shí)，最簡單的方法就是調(diào)用Object的hashCode方法，然后傳入該引用類型的屬性，讓hashCode方法只根據(jù)這幾個(gè)屬性來計(jì)算，那么實(shí)例相同的話，它們的hash值也會(huì)相等。等hashCode比較完后，如果相等再比較實(shí)例內(nèi)容，也就是equals，確保不是hash碰撞。

索引的分類

如果我們指定了一個(gè)主鍵，那么這個(gè)主鍵就是主鍵索引。如果我們沒有指定，Mysql就會(huì)自動(dòng)找一個(gè)非空的唯一索引當(dāng)主鍵。如果沒有這種字段，Mysql就會(huì)創(chuàng)建一個(gè)大小為6字節(jié)的自增主鍵。如果有多個(gè)非空的唯一索引，那么就讓第一個(gè)定義為唯一索引的字段當(dāng)主鍵，注意，是第一個(gè)定義，而不是建表時(shí)出現(xiàn)在前面的。

對(duì)于輔助索引來說，它們的B+樹結(jié)構(gòu)稍微有點(diǎn)特殊，它們的葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵，而不是整個(gè)數(shù)據(jù)。所以在大部分情況下，使用輔助索引查找數(shù)據(jù)，需要二次查找。但并不是所有情況都需要二次查找。比如查找的數(shù)據(jù)正好就是當(dāng)前索引字段的值，那么直接返回就行。這里提一句，B+樹的key就是對(duì)應(yīng)索引字段的內(nèi)容。

而輔助索引又有一些分類：唯一索引：不能出現(xiàn)重復(fù)的值，也算一種約束。普通索引：可以重復(fù)、可以為空，一般就是查詢時(shí)用到。前綴索引：只適用于字符串類型數(shù)據(jù)，對(duì)字符串前幾個(gè)字符創(chuàng)建索引。全文索引：作用是檢測大文本數(shù)據(jù)中某個(gè)關(guān)鍵字，這也是搜索引擎的一種技術(shù)。

注意，聚集索引、非聚集索引和前面幾個(gè)索引的分類并不是一個(gè)層面上的。上面的幾個(gè)分類是從索引的作用來分析的。聚集、非聚集索引是從索引文件上區(qū)分的。主鍵索引就屬于聚集索引，即索引和數(shù)據(jù)存放在一起，葉子節(jié)點(diǎn)存放的就是數(shù)據(jù)。數(shù)據(jù)表的.idb文件就是存放該表的索引和數(shù)據(jù)。

輔助索引屬于非聚集索引，說到這也就明白了。索引和數(shù)據(jù)不存放在一起的就是非聚集索引。在MYISAM引擎中，數(shù)據(jù)表的.MYI文件包含了表的索引， 該表的 葉子節(jié)點(diǎn)存儲(chǔ)索引和索引對(duì)應(yīng)數(shù)據(jù)的指針，指向.MYD文件的數(shù)據(jù)。

索引的幾點(diǎn)使用經(jīng)驗(yàn)

經(jīng)常被查詢的字段；經(jīng)常作為條件查詢的字段；經(jīng)常用于外鍵連接或普通的連表查詢時(shí)進(jìn)行相等比較字段；不為null的字段；如果是多條件查詢，最好創(chuàng)建聯(lián)合索引，因?yàn)槁?lián)合索引只有一個(gè)索引文件。

經(jīng)常被更新的字段、不經(jīng)常被查詢的字段、存在相同功能的字段

分享名稱：mysql樹高怎么計(jì)算,mysql b+樹高度
瀏覽路徑：http://m.kartarina.com/article22/hddscc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計(jì)公司、營銷型網(wǎng)站建設(shè)、微信小程序、App開發(fā)、網(wǎng)站維護(hù)、軟件開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)