MySQL-04：索引(一)

古城微笑少年丶 2022-12-22 09:06 74阅读 0赞

#### 1、索引 ####

索引的出现其实就是为了提高数据查询的效率，实质上就是将存储的数据按数据结构的方式存储起来。

对于数据库的表而言，每一张表都是多个索引实现。

#### 2、索引的简单实现 ####

索引常见的实现：哈希表，有序数组和搜索树。

**哈希表：** 哈希表方式，处理哈希碰撞用的是链表法，主要还是说说优缺点：单个数据查询或者新增数据很快，但是要区间查询数据就要遍历全部数据，所以哈希表适用于等值查询。

**有序数组：** 在进行等值查询和区间查询的时候效率很好，不过新增数据时就要挪动插入位置后面的数据，数组的特性嘛，适用于静态存储引擎。

**二叉搜索树：** 查询/删除或新增数据的时间复杂度都为nlog(n)

#### 3、索引的应用 ####

在数据库存储模型往往使用b+树 而不是二叉树，因为二叉树树高过高，每次查询都需要访问过多节点，即访问数据块过多，磁盘随机读取数据块过于耗时。 例如一个树高为20的二叉树，就最多需要访问20块数据块，如果访问一个数据块的时间为10ms，那最长时间就需要200ms。

如果采用N叉树，以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。当这棵树的树高为 4 时，就可以存储 1200 的 3 次方个值，一张17亿的表，至多需要访问4次即可查找到。

N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。这里的性能优异指的是磁盘IO次数少。

数据库主要是用来存储数据的，学习数据库的关键在于理解存储数据的数据模型，这样才能从理论上分析这个数据库的使用场景。

#### 4、索引的实现 ####

在MySQL中，索引是由存储引擎实现的，不同引擎之间索引的工作方式可能都不一样。

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表 。

**上面那句话可以解释如下：**

1.  在 InnoDB 中，每一张表对应的是多个 B+ 树，即一个主键索引树和多个非主键索引树。
2.  执行查询的效率：使用主键索引 > 使用非主键索引 > 不使用索引。
3.  如果不使用索引进行查询，则从主索引 B+ 树的叶子节点进行遍历。

来，看例子，例如，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。 表中 有5条数据R1R5，，R1R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵索引树的示例示意图如下。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NTM1_size_16_color_FFFFFF_t_70_pic_center]

左边的为主键索引数，右边的为非主键索引树。主键索引树的叶子节点存储的是整行数据，主键索引树也称为聚簇索引；非主键索引树的叶子节点存储的是主键的值，也被称为二级索引树。

主键索引树的每个叶子节点存储的是页(page)，页中有着多个行。

**基于主键索引和普通索引的查询有什么区别？**

*  如果语句是 select \* from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
 *  如果语句是 select \* from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。

基于非主键索引的查询需要多扫描一棵索引树，我们在应用中应该尽量使用主键查询。

#### 5、索引维护 ####

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。以上面这个图为例，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。

而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。

当相邻两个页删除了数据，导致利用率很低，会将数据页做合并。

自增主键： 插入新记录的时候可以不指定 ID 的值，系统会获取当前 ID 最大值加 1 作为下一条记录的 ID 值。

如果将带有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。

显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

下面这种情况适合使用业务字段做主键：

*  只有一个索引；
 *  该索引必须是唯一索引。

也就是典型的 KV 场景。

**练习问题：**

1.  什么是索引？索引出现的目的？
2.  实现索引的常见数据模型？每个模型之间的优缺点？
3.  数据库不选二叉树，而选用N叉数的原因？
4.  InnoDB中索引模型是什么？
5.  InnoDB中有几种不同的索引表？不同索引表之间的区别？
6.  对主键索引表和非主键索引表进行查询语句会发生什么？
7.  InnoDB是如何维护索引的？
8.  自增主键和业务主键之间的考量点？

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NTM1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/51c69e4c4d764fe48d5e6788e95355c3.png