首頁技術(shù)文章正文

索引的底層實(shí)現(xiàn)原理是什么？【大數(shù)據(jù)開發(fā)面試問題】

更新時(shí)間:2022年05月05日18時(shí)05分來源:傳智教育瀏覽次數(shù):

索引存儲(chǔ)在內(nèi)存中，為服務(wù)器存儲(chǔ)引擎為了快速找到記錄的一種數(shù)據(jù)結(jié)構(gòu)。索引的主要作用是加快數(shù)據(jù)查找速度，提高數(shù)據(jù)庫的性能。

索引的分類

(1) 普通索引：最基本的索引，它沒有任何限制。

(2) 唯一索引：與普通索引類似，不同的就是索引列的值必須唯一，但允許有空值。如果是組合索引，則列值的組合必須唯一。

(3) 主鍵索引：它是一種特殊的唯一索引，用于唯一標(biāo)識(shí)數(shù)據(jù)表中的某一條記錄，不允許有空值，一般用 primary key 來約束。

(4) 聯(lián)合索引(又叫復(fù)合索引)：多個(gè)字段上建立的索引，能夠加速復(fù)合查詢條件的檢索。

(5) 全文索引：老版本 MySQL 自帶的全文索引只能用于數(shù)據(jù)庫引擎為 MyISAM 的數(shù)據(jù)表，新版本 MySQL 5.6 的 InnoDB 支持全文索引。默認(rèn) MySQL 不支持中文全文檢索，可以通過擴(kuò)展 MySQL，添加中文全文檢索或?yàn)橹形膬?nèi)容表提供一個(gè)對(duì)應(yīng)的英文索引表的方式來支持中文。

1. 索引結(jié)構(gòu)

索引是在Mysql的存儲(chǔ)引擎(InnoDB,MyISAM)層中實(shí)現(xiàn)的, 而不是在服務(wù)層實(shí)現(xiàn)的. 所以每種存儲(chǔ)引擎的索引都不一定完全相同, 也不是所有的存儲(chǔ)引擎都支持所有的索引類型的, Mysql目前提供了以下4種索引:

B+Tree 索引: 最常見的索引類型, 大部分索引都支持B+樹索引.

Hash 索引: 只有Memory引擎支持, 使用場(chǎng)景簡(jiǎn)單.

R-Tree索引(空間索引): 空間索引是MyISAM引擎的一個(gè)特殊索引類型, 主要地理空間數(shù)據(jù), 使用也很少.

S-Full-text(全文索引): 全文索引也是MyISAM的一個(gè)特殊索引類型, 主要用于全文索引, InnoDB從Mysql5.6版本開始支持全文索引.

索引結(jié)構(gòu)

2. BTree結(jié)構(gòu)

B+Tree是在BTree基礎(chǔ)上進(jìn)行演變的, 所以我們先來看看BTree, BTree又叫多路平衡搜索樹, 一顆m叉BTree特性如下:

(1) 樹中每個(gè)節(jié)點(diǎn)最多包含m個(gè)孩子.

(2) 除根節(jié)點(diǎn)與葉子節(jié)點(diǎn)外, 每個(gè)節(jié)點(diǎn)至少有[ceil(m/2)] 個(gè)孩子(ceil函數(shù)指向上取整).

(3) 若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn), 則至少有兩個(gè)孩子.

(4) 每個(gè)非葉子節(jié)點(diǎn)由n個(gè)Key和n+1個(gè)指針組成, 其中 [ceil(m/2) -1 ] <= n <= m-1.

以5叉BTree為例, key的數(shù)量: 公式推導(dǎo) [ceil(m/2) -1 ] <= n <= m-1.

所以 2 <= n <= 4, 中間節(jié)點(diǎn)分裂父節(jié)點(diǎn),兩邊節(jié)點(diǎn)分裂.

Btree結(jié)構(gòu)

3.B+Tree 結(jié)構(gòu)

B+Tree為BTree的變種, B+Tree與BTree的區(qū)別:

1.B+Tree的葉子節(jié)點(diǎn)保存所有的key信息, 依key大小順序排列.

2.B+Tree葉子節(jié)點(diǎn)元素維護(hù)了一個(gè)單項(xiàng)鏈表.

所有的非葉子節(jié)點(diǎn)都可以看作是key的索引部分。

B+tree結(jié)構(gòu)

由于B+Tree只有葉子節(jié)點(diǎn)保存key信息, 查詢?nèi)魏蝛ey都要從root走的葉子. 所以B+Tree查詢效率更穩(wěn)定.

Mysql中的B+Tree

MySql索引數(shù)據(jù)結(jié)構(gòu)對(duì)經(jīng)典的B+Tree進(jìn)行了優(yōu)化, 在原B+Tree的基礎(chǔ)上, 增加了一個(gè)指向相鄰葉子節(jié)點(diǎn)的鏈表指針, 就形成了帶有順序指針的B+Tree, 提高區(qū)間訪問的性能.

MySql中的B+Tree索引結(jié)構(gòu)示意圖:

Mysql中的B+Tree