数据库索引

王小明_HIT

发布于 2020-05-29 16:13:08

6360

发布于 2020-05-29 16:13:08

文章被收录于专栏：程序员奇点程序员奇点

数据库索引

数据库索引，在日常工作中会经常接触到，比如某一个 SQL 查询比较慢，分析原因后，经常会说 “给某个字段加个索引”，索引又是如何工作的？

索引的出现是为了提高数据查询的效率，和书的目录是一样的。

索引常见的模型

哈希表

哈希表示一种以键值对（key-Value）存储数据的结构，我们只要输入待查找是值 key,就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置。然后把 value 放在数组的这个位置。有点类似 HashMap 的数据结构，多个key 值经过哈希函数的换算，会出现同一个值的情况，处理这种情况的一种方法是，拉出一个链表。

image

搜索指定 key 值的场景

图中，User2 和 User4 根据身份证号算出的值都是 N，但是没关系，后面有个列表，假设，这个是要查 ID_card_n2 对应的名字是什么，将 ID_card_n2 通过哈希值算出 N; 然后，按照顺序遍历，找到 User2。

搜索指定 key 范围的场景

如果按照索引结构支持范围查询，比如查身份证号在[ID_card_X，ID_card_Y] 区间的 User,可以先用二分法找到 ID_card_X (如果不存在 ID_card_X,就找到大于 ID_card_X 的第一个 User),然后向右遍历，知道查到第一个大于ID_card_Y的身份证号，退出循环。

如果仅仅看查询效率，这种 hash 表，有序数组是最好的数据结构，但是，在需要更新数据的时候，成本很高，需要往中间插入一个记录，就必须挪动后面索引的记录。

有序数组索引只适用于静态存储引擎比如你保存的数据 2019 年某个城市的人口数据，然后不再修改了。

二叉树排序树

二叉树排序树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。

如果这样要查 ID_card_n2 的话，按照下图中的顺序就是按照 UserA->UserC->UserF->User2 这个路径查找的 User2, 这个时间复杂度是 O(log(N))。为了维持O(log(N)),需要保持这棵树是平衡二叉树。

image

树可以是二叉树，也可以是多叉树，多叉数是每个阶段多个儿子，儿子从左到右保持递增，但是实际上大多数的数据库存储用的不是二叉树，索引不止存储在内存中，还要写到磁盘上。

你可以想象一下一棵100万节点的平衡二叉树，树高20.一次查询可能需要访问20个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要10ms左右的寻址时间。也就是说，对于一个100万行的表，如果使用二叉树来存储，单独访问一个行可能需要20个10ms的时间，这个查询可真够慢的。

B 树

B 树本质是多路二叉树；叶节点具有相同深度，叶节点的指针为空；所有索引元素不重复；节点中数据索引从左到右依次递增。

image

B+ 树

非叶子节点不存储数据，只存储索引（冗余）和指针，可以放更多的索引，树高度降低；叶子节点包含索引索引字段；叶子节点比 B 树增加了指针连接；叶子节点有双向指针连接（首尾节点可以通过指针连接），提高区间访问的性能，范围查找。

image

InnoDB 的索引模型

在 InnoDB 中，表都是需要根据主键顺序以索引形式存放，这种存储方式的表称为索引组织表，又因为前面我们提到的，InnoDB 使用 B+ 树索引模型，所以数据都是存储在 B+ 树中。

每个索引在 InnoDB 里面对应一颗 B+ 树。

假设，有一个主键列 ID 的表，表中有字段 k ,并且在 k 上有索引。

mysql> create table T(
id int primary key,
k int not null,
name varchar(16)，
index (k))engine=InnoDB；

表中R1 ~ R5的（ID,k）值分别为（100,1）、（200,2）、（300,3）、（500,5)和（600,6），两棵树的示例示意图如下。其中 ID 是主键，普通索引为 k;

普通索引和主键索引有啥区别？

主键索引的叶子节点存的是整行数据，在 InnoDB 里主键索引也被称为是聚簇索引（clustered index）。

非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引页称为二级索引（Secondary index）。

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

也就是说，基于非主键索引的查询要多扫描一棵索引树，因此我们需要尽量用主键查询。

为什么非主键索引结构叶子节点存储的是主键值

主键索引和非主键索引维护各自的B+树结构，当插入的数据的时候，由于数据只有一份，通过非主键索引获取到主键值，然后再去主键索引的B+树数据结构中找到对应的行数据，节省了内存空间；
如果非主键索引的叶子节点也存储一份数据，如果通过非主键索引插入数据，那么要向主键索引对应的行数据进行同步，那么会带来数据一致性问题。可以通过事务的方式解决，我们都知道使用事务后，就会对性能有所消耗。

为什么InnoDB推荐使用整型的自增主键？

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

索引的数据类型是整型，一方面整型占有的磁盘空间或内存空间相比字符串更少，另一方面整型比较比字符串比较更快速，字符串比较是先转换为ASCII码，然后再比较的。
最后，B+树本质是多路多叉树，如果主键索引不是自增的，那么后续插入的索引就会引起B+树的其他节点的分裂和重新平衡，影响数据插入的效率，如果是自增主键，只用在尾节点做增加就可以。从性能和存储空间方面考量，自增主键往往是更合理的选择。

Innodb 逻辑存储结构图

从上往下依次为：Tablespace、Segment、Extent、Page 以及 Row。

Page 结构

Page 数据结构，File Header 字段用于记录 Page 的头信息，其中比较重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段，通过这两个字段，我们可以找到该页的上一页和下一页，实际上所有页通过两个字段可以形成一条双向链表。Page Header 字段用于记录 Page 的状态信息。接下来的 Infimum 和 Supremum 是两个伪行记录，Infimum（下确界）记录比该页中任何主键值都要小的值，Supremum （上确界）记录比该页中任何主键值都要大的值，这个伪记录分别构成了页中记录的边界。