1.什么是索引？

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

2.為什么需要索引？

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

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

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

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

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

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

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

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

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

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

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

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

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

5.哈希表

上面是哈希表的存儲(chǔ)結(jié)構(gòu)，我們來(lái)探討這類的存儲(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è)遍歷
• 對(duì)于內(nèi)存空間的要求比較高（要把全部數(shù)據(jù)加到到內(nèi)存中）
  

優(yōu)點(diǎn)：
如果是等值查詢，那么會(huì)非?？?/p>

那么在mysql中有沒(méi)有hash索引呢？

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

 6.樹(shù)

6.1 二叉樹(shù)

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

6.2 二分查找樹(shù)（Binary Search Tree ,BST）

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

6.3 平衡二叉樹(shù)（Balanced Binary Tree, AVL樹(shù)）

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

6.4 紅黑樹(shù)

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

6.5 B樹(shù)

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

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

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

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

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

6.6 B+樹(shù)

B樹(shù)到B+樹(shù)的演變：非葉子節(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萬(wàn)）條記錄

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

答：保證key的長(zhǎng)度越小也好，varchar小于4字節(jié)用varcahr，大于4字節(jié)用int

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

總結(jié)

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

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

最新評(píng)論