Mysql索引底層數(shù)據(jù)結(jié)構(gòu)與算法-創(chuàng)新互聯(lián)

一、索引 1、索引簡(jiǎn)介

索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)

創(chuàng)新互聯(lián)專注于老城企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站開(kāi)發(fā),商城開(kāi)發(fā)。老城網(wǎng)站建設(shè)公司,為老城等地區(qū)提供建站服務(wù)。全流程按需網(wǎng)站建設(shè)，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)2、索引數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)可視化：Data Structure Visualization

2.1、二叉樹(shù)

特點(diǎn)

左子節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)值小，右子節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)值大

存在的問(wèn)題

如上圖，當(dāng)進(jìn)行順序新增數(shù)據(jù)時(shí)，二叉樹(shù)就變成單邊的”鏈條“，這樣查找數(shù)據(jù)的效率就變慢了。

例如查找5，就要經(jīng)過(guò)5次查找。

2.2、紅黑樹(shù)

特點(diǎn)

節(jié)點(diǎn)是紅色或者黑色
根節(jié)點(diǎn)是黑色
每個(gè)葉子的節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NULL）
每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的。
從任意節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同的黑色節(jié)點(diǎn)

存在的問(wèn)題

紅黑樹(shù)和二叉樹(shù)對(duì)比，在一定程度上解決單邊過(guò)長(zhǎng)的問(wèn)題，但它存儲(chǔ)高度的問(wèn)題。如果數(shù)據(jù)量過(guò)大，IO次數(shù)更多，性能損耗更大

2.3、Hash表

例如圖中查找Tom，只要通過(guò)一次hash計(jì)算就可以確定數(shù)據(jù)所在的位置。

優(yōu)點(diǎn)

對(duì)索引的key進(jìn)行一次hash計(jì)算就可以定位出數(shù)據(jù)存儲(chǔ)的位置

存在的問(wèn)題

Hash索引只能進(jìn)行等于、不等于、IN 等查詢，不支持范圍查詢；若是要進(jìn)行范圍查詢，hash索引的時(shí)間復(fù)雜度會(huì)退化為O(n)
Hash表的數(shù)據(jù)是沒(méi)有順序的，在ORDER BY 情況下，還需要對(duì)數(shù)據(jù)重新排序
在等值查詢時(shí)，若是索引列的重復(fù)值過(guò)多，就會(huì)觸發(fā)Hash沖突，每次沖突都需要遍歷桶排序中的指針來(lái)進(jìn)行

2.4、B-Tree

B-Tree 是一種平衡的多路查找（又稱排序）樹(shù)，MongoDB索引默認(rèn)的存儲(chǔ)結(jié)構(gòu)使用的就是B-Tree

特點(diǎn)

葉子節(jié)點(diǎn)具有相同深度
葉節(jié)點(diǎn)的指針為空
節(jié)點(diǎn)中的數(shù)據(jù)索引從左到右遞增排列
節(jié)點(diǎn)中存儲(chǔ)data數(shù)據(jù)

存在的問(wèn)題

B-Tree每個(gè)節(jié)點(diǎn)中含有data值。而每次取一頁(yè)數(shù)據(jù)（16KB），將會(huì)導(dǎo)致每次取一頁(yè)的索引數(shù)據(jù)就比較少。當(dāng)數(shù)據(jù)量很大的時(shí)候，同樣會(huì)導(dǎo)致B-Tree樹(shù)的高度比較大，也會(huì)影響查詢效率。所以引入B+Tree
B-Tree的范圍查找每次都要從根節(jié)點(diǎn)重新查找

2.5、B+Tree

B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化，MySQL索引默認(rèn)的存儲(chǔ)結(jié)構(gòu)使用的就是B+Tree。

特點(diǎn)：

非葉子節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)索引(冗余)，可以放更多的索引
葉子節(jié)點(diǎn)包含所有索引字段
葉子節(jié)點(diǎn)用指針連接，提高區(qū)間訪問(wèn)的性能，例如范圍查找

假如：以一個(gè)高度為3的B+Tree為例，B+Tree的表都存滿了，能存儲(chǔ)多少數(shù)據(jù)？

SHOW GLOBAL STATUS like 'Innodb_page_size';

假設(shè)主鍵id為bigint類型，長(zhǎng)度就是8B，指針大小為6B，一共就是14B，假設(shè)最后一層，存放的數(shù)據(jù)data大小為1kb

第一層大節(jié)點(diǎn)數(shù)為： 16k / (8B + 6B) = 1170 (個(gè))

第二層大節(jié)點(diǎn)數(shù)也應(yīng)為：1170個(gè)

第三層大節(jié)點(diǎn)數(shù)為：16k / 1k = 16 (個(gè))

所以一張B+Tree的表最多存放 1170 * 1170 * 16 = 21902400 ≈ 2千萬(wàn)。

B+Tree結(jié)構(gòu)的表可以容納千萬(wàn)數(shù)據(jù)量的查詢。而且一般來(lái)說(shuō)，MySQL會(huì)把 B+Tree 根節(jié)點(diǎn)放在內(nèi)存中，那只需要兩次磁盤IO（第二層1次，第三層1次）

二、存儲(chǔ)引擎 1、MySIAM存儲(chǔ)引擎(非聚集)

MyISAM索引文件和數(shù)據(jù)文件是分開(kāi)的，數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)、索引在磁盤中文件有三個(gè)，

.frm 文件存儲(chǔ)數(shù)據(jù)表定義

.MYI存儲(chǔ)索引

.MYD存儲(chǔ)實(shí)際數(shù)據(jù)

葉子結(jié)點(diǎn)中的data存儲(chǔ)的都是該行數(shù)據(jù)對(duì)應(yīng)的磁盤指針，根據(jù)指針再去.MYD拿數(shù)據(jù)

2、InnoDB存儲(chǔ)引擎(聚集)

InnoDB存儲(chǔ)引擎它的表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個(gè)索引文件。不同于MyISAM存儲(chǔ)引擎是，數(shù)據(jù)不分離。

.frm文件存儲(chǔ)數(shù)據(jù)表定義

.ibd文件存放的索引和實(shí)際數(shù)據(jù)

聚集索引

非聚集索引

三、聯(lián)合索引

比較name再比較age再比較position，如果第一個(gè)字段相等，看第二個(gè)字段。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)題目：Mysql索引底層數(shù)據(jù)結(jié)構(gòu)與算法-創(chuàng)新互聯(lián)
文章位置：http://muchs.cn/article32/dhecsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開(kāi)發(fā)、企業(yè)建站、網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)公司、搜索引擎優(yōu)化、電子商務(wù)

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

猜你還喜歡下面的內(nèi)容