文章

Innodb - 索引

发表于 更新于
作者 puppylpg 31 分钟阅读

在Innodb - 页中，介绍了页内行记录的排列方式——类似于一个拥有一层目录的跳表，可以加速行的定位。既然现在页与页之间也构成了双向链表，那么类比页内跳表，可以在页与页之间构建一个页间跳表，以加速页的定位。

  1. 有序是前提
  2. 索引
    1. 再来一页
    2. 再来一层
    3. 那它为什么不叫跳表？
      1. 层级意味着IO次数
    4. 根节点怎么找
  3. 查找记录
  4. 索引类型
    1. 聚簇索引
    2. 二级索引
    3. 联合索引
  5. MyISAM：索引是索引，数据是数据
  6. 索引的代价
    1. 回表
    2. 索引条件下推
  7. 索引优化
    1. 减少回表
      1. limit 1
      2. select *
      3. 索引列不要有太多重复值
    2. 减小记录项
      1. 索引列的类型尽量小
      2. 为列前缀建索引
  8. 语法
  9. B树？

有序是前提

链表之所以能建跳表，前提是是链表必须有序。

如果想把页作为链表的一个节点，给页之间建立跳表，就 必须让页与页之间的记录是主键有序的：下一页的所有记录的主键值都必须大于上一页记录的所有主键值。

怎么保证页与页之间的记录有序？

  1. 当记录只有一页时，行与行之间通过链表保证有序，这是必然的，因为一行只有一个主键，按照主键大小构建链表就行了；
  2. 当记录太多，一页放不下时，就要进行页分裂，用两个页存放记录。分裂的时候，按照主键大小把主键比较大的那一半记录放到下一页就行；

只有页与页之间的主键有序，才能把页看做节点建立跳表。

索引

类比页内跳表的构建方式，每个page可以选出一个带头大哥，innodb选了page里 用户插入的 主键最小的那条记录（page内最小的记录是infimum），所以可以称为“page的带头小哥”，记录它的：

  • 主键值；
  • 所在页号；

这里并没有完整抽出带头小哥的记录内容，只需要知道它的主键和页号就行了，具体内容需要去它页号对应的page里找。

每个页选一个带头小哥，构成了页的一级目录。现在整个结构长得开始像跳表了。

再来一页

如果自己观察这些带头小哥，可以发现：抽出来的行记录，还是行记录。把这些带头小哥的行记录也用指针连起来，又构成了一个有序双向链表！

接着精彩的地方来了——这些带头小哥长得跟行记录很像，所以相邻的一堆带头小哥们也可以放到page里，就像行记录放到page里一样！如此一来，小哥们就可以像其他page用相同的方式进行管理了！

之前说过，带头小哥的行记录内容比较简单，只记录了两个列：

  • 主键值；
  • 页号；

它没有记录数据的行记录的完整数据信息（所有的列的内容），所以为了和数据行以示区分，它的metadata的record_type=1，标志着这个行是一个目录行，而不是数据行。

Innodb - 行里介绍了record_type有四种：0-用户插入的数据记录；1-目录项记录；2-infimum；3-supremum。

再来一层

带头小哥多了，和用户插入的数据行一样，一页也放不下了，自然就组成了多个page。

另一个精彩的地方来了——是不是还可以继续再给这些page抽出来一个个代表这些page的带头小哥？相当于给刚刚装着带头小哥的页又创建了新一层目录……

这样层层构建，就是一个长得像跳表的东西——它就是B+树：

  • 最底层的存放数据项的页是B+树的叶节点，记录的是数据的完整内容；
  • 叶节点上层的数据页是B+树中间结点，他们都是存放目录项的页；

当开始套娃的时候，人类的脑子逐渐跟不上的时候，精彩的事情就来了！高分电影不都是这个套路吗？而这些被人们奉若神明的高分套路，在计算机里可太平平无奇了:D

那它为什么不叫跳表？

尬住了……一直说它像跳表，怎么像到最后，它叫B+树了？

B+树和跳表确实很像，都有多层，上一层是下一层的目录，所以节点自下往上越来越少。

层级意味着IO次数

b+树听起来是一个很多层的结构，但MySQL的索引真的有很多层吗？

假设一个页能存放100条数据记录，或者1000条目录项记录（因为一条目录项记录只需要记录主键和页号，所以空间占用远少于数据项）：

  1. 一层B+树，叶子节点能存放100条数据；
  2. 两层B+树，叶子节点能存放100*1000=10w条数据；
  3. 三层B+树，叶子节点能存放10w*1000=1亿条数据；
  4. 四层B+树，叶子节点能存放1亿*1000=1000亿条数据；

事实上一个表一般最多存几千万条，也就是说3层B+数就够了。此时按照主键寻找一条记录，从根目录起，只需要找三层。也就是说查询一次数据，如果这些数据页都在磁盘里，那么最多需要查询三次磁盘IO。

跳表是链表结构，一条数据一个结点，如果最底层要存放2kw数据，且每次查询都要能达到二分查找的效果，2kw大概在2的24次方左右，所以，跳表大概高度在24层左右。最坏情况下，这24层数据会分散在不同的数据页里，即查一次数据会经历24次磁盘IO。

因此存放同样量级的数据，B+树的高度比跳表的要少，如果放在mysql数据库上来说，就是磁盘IO次数更少，因此B+树查询更快。所以以页为单位管理的B+树特别适合磁盘存储。一次读取一页，减少磁盘io。而跳表没有以页为单位的概念，所以适合放在内存里。

  • https://stackoverflow.com/a/23814116/7676237
  • https://ost.51cto.com/posts/11398

在内存里，层级更低的B+树失去了优势，同时劣势也更加明显。因为B+树维护成本比较高，需要考虑页分裂等操作。但是跳表的插入非常简单！关于跳表插入时的层级构建，实际上所有的主流跳表实现（比如redis的zset）都很简单：只需要在插入一个节点的时候，随机决定该节点要不要作为目录、做为多少层目录

1
2
3
4
5
6
7
8
9
10
11

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

因此跳表独立插入，并根据随机函数确定层数，没有旋转和维持平衡的开销，使得它写入性能会比B+树要好。

事实上，facebook造了个rocksDB的存储引擎，里面就用了跳表。相当于在磁盘上用跳表。它的写入性能确实是比innodb要好（没有页分裂），但读性能确实比innodb要差不少（io次数过多）。

因此，redis这种内存型数据库使用跳表，MySQL这种磁盘存储型数据库使用b+树。

B+树适合读多写少，跳表写性能更好，但是在磁盘的场景下，读性能差。

根节点怎么找

看出来了，每一次查找都是从根节点开始找的。那怎么找到根节点？

当插入第一条记录的时候，innodb创建了第一个页，存放数据。这种情况下，其实是没有目录项的。

一页都放不满，要什么目录项！直接在页内做个二分查找就够了。

后来随着数据的增多，一页放不下，就开始 页分裂，此时出现了下一层节点。而原来创建的第一个节点，就成了树的根节点！后面再怎么分裂下去，根节点永远是第一个创建的页，所以它的页号永远不变。

那就简单了，只要在为表插入第一条数据创建第一个页的时候，把页号记下来，就可以知道聚簇索引根节点的页号了。

查找记录

现在查找记录就两步：

  1. 使用索引（页间跳表）定位到记录所在的页；
  2. 使用页内跳表，定位到数据行的具体位置；

索引类型

聚簇索引

这种B+树，子节点是数据记录项，其他节点是目录项，索引本身也是数据，所以被称为聚簇索引。

以主键为顺序构造的索引，就是聚簇索引，而这种索引是默认创建的。之前Innodb - 行说如果用户不显式创建主键，也没有unique not null项，就会自己创建一个隐藏列row_id作为主键。innodb对主键这么执着，就是为了在这里创建聚簇索引。

索引即数据，数据即索引。存储数据项的时候，默认就构建了一个B+树索引。

二级索引

根据MySQL的语法，还可以为其他列构建索引，以加快对该列的搜索。这种情况下，不是以主键构造的索引，而是按照该列的值新建了一棵B+树。

又一棵B+树，它的叶子节点里也都是用户输入的数据项吗？显然不是，否则每多建一个索引，MySQL数据空间占用岂不是翻倍了？

所以这里用的是用指针。这种B+树的叶子节点的数据项实际就两列：

  • 目标索引列的值；
  • 对应的主键值；

也就是说，它的数据项是不完整的原始数据项，只有其中的主键列和目标索引列。

而非叶子节点的目录项和聚簇索引没什么差别：

  • 目标索引列的值；
  • 对应的主键值；
  • 页号；

这里需要主键值，主要是因为索引列可能有重复值，搭配上主键，就是唯一的了。此时就算插入相同索引列值的数据，也可以再按照主键值确定插入的前后位置。

这种B+树索引叫二级索引：每次按照目标索引列查记录，先查二级索引，定位到主键值，再根据主键值查找聚簇索引，查找原始数据项。

和聚簇索引按照主键值的大小有序排列一样，二级索引按照索引列值的大小有序排列。

它叫二级索引，因为还要再用一次聚簇索引。而这种再查聚簇索引的过程，叫做 回表，就好像又回到了原始的数据表再查一次一样。

二级索引和聚簇索引的另一个区别在于，因为索引列不是主键，所以可能有重复值，因此查找索引列的值的时候，查到的可能是很多条主键值，那就要根据每一条主键值进行多次回表。

联合索引

另一种MySQL创建索引的语法，以多个列共同建立一个索引，叫做联合索引。

它的思路和二级索引是一模一样的，毕竟换个角度来看，二级索引就是只有一个索引列的联合索引。

二级索引只是表面上看只有一个索引列，其实更准确点儿说，是索引列和主键值的联合索引。

因此联合索引的非叶子节点：

  • 各个联合索引列的值；
  • 主键值；
  • 页号；

联合索引的叶子节点的值：

  • 各个联合索引列的值；
  • 主键值；

联合索引先按照第一个索引列的值有序排列，再按照第二个索引列的值有序排列，直到最后一个索引列。

MyISAM：索引是索引，数据是数据

MyISAM和innodb不一样，它的行也是连续存放的，但没有页的概念，行与行之间也不构成链表。

MyISAM也会默认按照主键建立索引，索引也是B+树，但是树是独立于行记录的，它的叶子节点不是行记录数据，而是主键值、行地址。 所以MyISAM的索引就像Innodb的二级索引一样，想查到原始数据，一定要进行一次回表！但是因为它记录了数据行的行地址，所以直接就定位到行了，而不是像Innodb一样从聚簇索引的根一层层找到叶子节点的原始数据。

虽然要回表，但是MyISAM的回表速度很快，所以在速度上其实和Innodb没啥太大区别。

MyISAM按照非主键建立的索引，和按照主键建立的索引几乎没区别，就是把主键换成了索引列。MyISAM的二级索引不需要存储主键值了，它也记录下了数据行的行地址，直接就可以定位到数据行了。

MyISAM的列索引之所以不需要主键，是因为访问数据的时候不需要主键，直接用行数据的地址。Innodb的二级索引一定要用主键，是因为数据在聚簇索引里，而举措索引是以主键建的索引。

所以MyISAM里的所有索引都相当于Innodb的二级索引。而且索引是不是以主键构建的，也并不重要了。有行地址了，还怕找不到数据？

MyISAM的索引放在单独的索引文件，数据放在单独的数据文件，二者物理上是分离的，所以：索引是索引，数据是数据。

索引的代价

索引这么强大，为什么不给所有列都加上索引呢？

索引有一些显而易见的开销：

  • 空间换时间：多占用存储；
  • 时间换时间：增加了增删的时间以换取查询的时间；

所以如果不怎么查某个列，就别对这个列建索引了，不然枉费一大堆空间时间。

但这还不是全部——

回表

对于innodb的二级索引来说，使用索引意味着：

  1. 先根据索引列的值查到主键值；
  2. 再按照主键值回到聚簇索引查询真正的数据行，也就是回表；

回表意味着要把聚簇索引对应的page从磁盘加载到内存中，需要额外的磁盘io代价。如果索引列非unique，那大概率会找到多条主键值，这些主键值很可能不连续，所有的主键值都要回表，就会产生大量的随机IO。

所以有时候，某些查询宁愿全表扫描，也不使用二级索引。与产生一大堆随机io，还不如全表扫描产生连续io更迅速。

至于什么时候使用二级索引，什么时候全表扫描，会由查询优化器去估计。只是估计，未必准确。但是如果二者的代价有数量级上的区别，就比较好选择更优的那个。

索引条件下推

其实这是一个很理所当然的思路，但是好像是个比较火的名词，就特别记录一下。

假设一个联合索引用了col1，col2，col3，sql查询是select * from table where col1 = 'a' and col3 = 'c'。本来，在没有col1或者col3的单独二级索引的情况下，应该：

  1. 使用联合索引搜索所有col1=a的列的主键；
  2. 然后给这些主键回表；
  3. 根据回表得到的值，再判断col3是不是c。

但是既然col3已经在联合索引里了，不如先行判断所有col1=a的列的col3是不是c，是的话再回表。这样就减少了很多回表次数！所以被称为Index Condition Pushdown：先pushdown索引条件，比较c3，再决定是否回表。

索引优化

由上可知，索引的代价主要是回表带来的。而回表慢就慢在要从磁盘上加载page。

那么优化索引查询可以有以下两个思路：

  1. 减少回表次数；
  2. 减小记录项的大小，以增大page可容纳的记录数：每页多装点儿，回一次表就能多读取到几条记录，总体而言减少了回表次数。本质上还是为了减少回表次数；

减少回表

limit 1

select尽量加limit 1，最多最多回表一次 :D

select *

没事儿别老select *。按照二级索引或者联合索引检索的时候，尽量select二级索引、联合索引里的值，这样就不用回表到聚簇索引查找所有列的值了。

比如：

1

select key1, key2 from table where key1 = xxx

只需要查key1和key2的联合索引就行了，不用回表。

索引列不要有太多重复值

不然这个二级索引一查查到一堆值相等的记录，就会产生一堆回表操作。

减小记录项

索引列的类型尽量小

比如数值列做索引，能用tinyint就不用int，能用int就不用bigint。

既可以减少数据记录项的大小，该列又是索引项，也可以减少目录项的大小，目录页还能多装几条索引。

这条建议尤其适合主键，因为无论是数据项、聚簇索引、二级索引，都带主键值。所以主键类型选的尽量小，大家的数据项都能减小。

为列前缀建索引

字符串列作为索引列，不一定非得给完整的字符串建索引。假设前十个字符已经比较有区分度了，就可以用这一列的前十个字符串做索引。

按照key1列的前十个字符做索引，索引名为idx_key1：

1

ALTER TABLE t1 ADD INDEX idx_key1(key1(10));

但这样会损害索引的另一个功能：排序。本来如果查询结果要按照key1排序，索引其实本身就是按key1排好序的，可以直接用。现在因为key1这个索引不是完整的索引，而是前缀索引，就没办法用于排序了。只能和没有索引的列一样，先进行全表扫描，再进行文件排序了。

语法

使用KEY或者INDEX创建索引，二者等价。

新建：

1
2
3
4
5
6

CREATE TABLE t1 (
    c1 INT,
    c2 INT
    PRIMARY KEY(c1),
    INDEX idx_c2(c2)
) CHARSET=utf8mb4 ENGINE=INNODB ROW_FORMAT=COMPACT;

index最好自己起个名字，最好是idx+列名。否则MySQL会自动给index起个名字。有名字了，删也好删：

1

ALTER TABLE t1 DROP INDEX idx_c2;

新增：

1

ALTER TABLE t1 ADD (INDEX|KEY) idx_c2(c2);

B树？

提及B+树，就不得不提一下B树。

B树和B+树是两种常用的平衡搜索树数据结构，它们的区别如下：

  1. 存储方式：B树的每个节点既存储数据，又存储索引；而B+树的内部节点只存储索引，所有的数据都存储在叶子节点上。
  2. 叶子节点链接：B树的叶子节点之间没有链接，它们是通过内部节点进行连接；而B+树的叶子节点通过链表或其他方式进行连接，形成了一个有序链表。
  3. 范围查询：B树进行范围查询时需要在内部节点和叶子节点之间进行多次跳跃；而B+树的范围查询非常高效，因为它的叶子节点形成了一个有序链表，可以直接顺序遍历。
  4. 数据位置：B树的数据可以存储在任意节点中，查询时可能需要在整棵树中进行搜索；而B+树的数据只存储在叶子节点中，查询时只需要搜索叶子节点，提高了查询效率。

所以B+树的数据比较紧凑，只在叶子节点上，而且因为叶子之间是链表，可以做遍历操作。常用于range查找。

仅range遍历这一点，B树就不适合做数据库的数据结构了。

当然，和B+树类似的跳表是可以range的。

mysql, innodb, skiplist
mysql innodb skiplist
本文由作者按照 CC BY 4.0 进行授权