一、索引 1、索引簡介

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

創(chuàng)新互聯(lián)專注于老城企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站開發(fā),商城開發(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、二叉樹

特點(diǎn)

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

存在的問題

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

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

2.2、紅黑樹

特點(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)

存在的問題

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

2.3、Hash表

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

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

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

存在的問題

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

2.4、B-Tree

B-Tree 是一種平衡的多路查找（又稱排序）樹，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ù)

存在的問題

• B-Tree每個(gè)節(jié)點(diǎn)中含有data值。而每次取一頁數(shù)據(jù)（16KB），將會(huì)導(dǎo)致每次取一頁的索引數(shù)據(jù)就比較少。當(dāng)數(shù)據(jù)量很大的時(shí)候，同樣會(huì)導(dǎo)致B-Tree樹的高度比較大，也會(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ū)間訪問的性能，例如范圍查找

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

SHOW GLOBAL STATUS like 'Innodb_page_size';

假設(shè)主鍵id為bigint類型，長度就是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千萬。

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

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

MyISAM索引文件和數(shù)據(jù)文件是分開的，數(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ù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：Mysql索引底層數(shù)據(jù)結(jié)構(gòu)與算法-創(chuàng)新互聯(lián)
URL標(biāo)題：http://weahome.cn/article/dhecsc.html