一、索引 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è)計，全程項目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)2、索引數(shù)據(jù)結(jié)構(gòu)

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

2.1、二叉樹

特點

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

存在的問題

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

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

2.2、紅黑樹

特點

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

存在的問題

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

2.3、Hash表

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

優(yōu)點

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

存在的問題

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

2.4、B-Tree

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

特點

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

存在的問題

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

2.5、B+Tree

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

特點：

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

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

SHOW GLOBAL STATUS like 'Innodb_page_size';

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

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

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

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

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

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

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

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

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

.MYI存儲索引

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

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

2、InnoDB存儲引擎(聚集)

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

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

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

聚集索引

非聚集索引

三、聯(lián)合索引

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

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

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

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

廣告

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