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

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

索引的分類

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

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

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

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

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

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

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

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

Hash 索引: 只有Memory引擎支持, 使用場景簡單.

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

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

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

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

(1) 樹中每個節(jié)點最多包含m個孩子.

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

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

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

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

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

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

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

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

2.B+Tree葉子節(jié)點元素維護了一個單項鏈表.

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

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

Mysql中的B+Tree

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

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

Mysql索引如何使使用?怎么創(chuàng)建索引？

Pandas算術(shù)運算和數(shù)據(jù)對齊【Pandas索引操作演示】

用花式索引或布爾索引訪問元素【索引的基本用法】

MongoDB中的索引分為幾類？

傳智教育python+大數(shù)據(jù)開發(fā)培訓課程