MySQL-04：索引一

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

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

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

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

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

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

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

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

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

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

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

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

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

来，看例子，例如，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。表中有5条数据R1_R5，，R1R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵索引树的示例示意图如下。
MySQL-04：索引一

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

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

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

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

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

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

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

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

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

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

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

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

也就是典型的 KV 场景。

练习问题：