数据结构与数据库索引
# 数据结构与数据库索引
关键词：链表、数组、散列表、红黑树、B+ 树、LSM 树、跳表
# 引言
数据库是“按照 数据结构 来组织、存储和管理数据的仓库”。是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集合。
——上面这句定义对数据库的定义来自百度百科。通过这个定义，我们也能明显看出数据结构是实现数据库的基石。
从本质来看，数据库只负责两件事：读数据、写数据；而数据结构研究的是如何合理组织数据，尽可能提升读、写数据的效率，这恰好是数据库的核心问题。因此，数据结构与数据库这两个领域有非常多的交集。其中，数据库索引最能体现二者的紧密关联。
索引是数据库为了提高查找效率的一种数据结构。索引基于原始数据衍生而来，它的主要作用是缩小检索的数据范围，提升查询性能。通俗来说，索引在数据库中的作用就像是一本书的目录索引。索引对于良好的性能非常关键，在数据量小且负载较低时，不恰当的索引对于性能的影响可能还不明显；但随着数据量逐渐增大，性能则会急剧下降。因此，索引优化应该是查询性能优化的最有效手段。
很多数据库允许单独添加和删除索引，而不影响数据库的内容，它只会影响查询性能。维护额外的结构势必会引入开销，特别是在新数据写入时。对于写入，它很难超过简单地追加文件方式的性能，因为那已经是最简单的写操作了。由于每次写数据时，需要更新索引，因此任何类型的索引通常都会降低写的速度。
本文以一些常见的数据库为例，分析它们的索引采用了什么样的数据结构，有什么利弊，为何如此设计。
# 数组和链表
数组和链表分别代表了连续空间和不连续空间的存储方式，它们是线性表（Linear List）的典型代表。其他所有的数据结构，比如栈、队列、二叉树、B+ 树等，实际上都是这两者的结合和变化。
数组用连续的内存空间来存储数据。数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。但这并不代表数组的查找时间复杂度也是 O(1)。
- 对于无序数组，只能顺序查找，其时间复杂度为
O(n)。 - 对于有序数组，可以应用二分查找法，其时间复杂度为
O(log n)。
在有序数组上应用二分查找法如此高效，为什么几乎没有数据库直接使用数组作为索引？这是因为它的限制条件：数据有序——为了保证数据有序，每次添加、删除数组数据时，都必须要进行数据调整，来保证其有序，而 数组的插入/删除操作，时间复杂度为 O(n)。此外，由于数组空间大小固定，每次扩容只能采用复制数组的方式。数组的这些特性，决定了它不适合用于数据频繁变化的应用场景。
链表用不连续的内存空间来存储数据；并通过一个指针按顺序将这些空间串起来，形成一条链。
区别于数组，链表中的元素不是存储在内存中连续的一片区域，链表中的数据存储在每一个称之为「结点」复合区域里，在每一个结点除了存储数据以外，还保存了到下一个节点的指针（Pointer）。由于不必按顺序存储，链表的插入/删除操作，时间复杂度为 O(1)，但是，链表只支持顺序访问，其 查找时间复杂度为 O(n)。其低效的查找方式，决定了链表不适合作为索引。
# 哈希索引
哈希表是一种以键 - 值（key-value）对形式存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 Value。
哈希表 使用 哈希函数 组织数据，以支持快速插入和搜索的数据结构。哈希表的本质是一个数组，其思路是：使用 Hash 函数将 Key 转换为数组下标，利用数组的随机访问特性，使得我们能在 O(1) 的时间代价内完成检索。
有两种不同类型的哈希表：哈希集合 和 哈希映射。
- 哈希集合 是集合数据结构的实现之一，用于存储非重复值。
- 哈希映射 是映射 数据结构的实现之一，用于存储键值对。
哈希索引基于哈希表实现，只适用于等值查询。对于每一行数据，哈希索引都会将所有的索引列计算一个哈希码（hashcode），哈希码是一个较小的值。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
✔ 哈希索引的优点：
- 因为索引数据结构紧凑，所以查询速度非常快。
❌ 哈希索引的缺点：
- 哈希索引值包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能影响不大。
- 哈希索引数据不是按照索引值顺序存储的，所以无法用于排序。
- 哈希索引不支持部分索引匹配查找，因为哈希索引时使用索引列的全部内容来进行哈希计算的。如，在数据列 (A,B) 上建立哈希索引，如果查询只有数据列 A，无法使用该索引。
- 哈希索引只支持等值比较查询，包括
=、IN()、<=>；不支持任何范围查询，如WHERE price > 100。 - 哈希索引有可能出现哈希冲突
- 出现哈希冲突时，必须遍历链表中所有的行指针，逐行比较，直到找到符合条件的行。
- 如果哈希冲突多的话，维护索引的代价会很高。
因为种种限制，所以哈希索引只适用于特定的场合。而一旦使用哈希索引，则它带来的性能提升会非常显著。例如，Mysql 中的 Memory 存储引擎就显示的支持哈希索引。
# B-Tree 索引
通常我们所说的 B 树索引是指 B-Tree 索引，它是目前关系型数据库中查找数据最为常用和有效的索引，大多数存储引擎都支持这种索引。使用 B-Tree 这个术语，是因为 MySQL 在 CREATE TABLE 或其它语句中使用了这个关键字，但实际上不同的存储引擎可能使用不同的数据结构，比如 InnoDB 使用的是 B+Tree索引；而 MyISAM 使用的是 B-Tree索引。
B-Tree 索引中的 B 是指 balance，意为平衡。需要注意的是，B-Tree 索引并不能找到一个给定键值的具体行，它找到的只是被查找数据行所在的页，接着数据库会把页读入到内存，再在内存中进行查找，最后得到要查找的数据。
# 二叉搜索树
二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。其查询时间复杂度是 O(log n)。
当然为了维持 O(log n) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log n)。
随着数据库中数据的增加，索引本身大小随之增加，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 I/O 消耗，相对于内存存取，I/O 存取的消耗要高几个数量级。可以想象一下一棵几百万节点的二叉树的深度是多少？如果将这么大深度的一颗二叉树放磁盘上，每读取一个节点，需要一次磁盘的 I/O 读取，整个查找的耗时显然是不能够接受的。那么如何减少查找过程中的 I/O 存取次数？
一种行之有效的解决方法是减少树的深度，将二叉树变为 N 叉树（多路搜索树），而 B+ 树就是一种多路搜索树。
# B+Tree 索引
B+ 树索引适用于全键值查找、键值范围查找和键前缀查找，其中键前缀查找只适用于最左前缀查找。
理解 B+Tree，只需要理解其最重要的两个特征即可：
- 第一，所有的关键字（可以理解为数据）都存储在叶子节点，非叶子节点并不存储真正的数据，所有记录节点都是按键值大小顺序存放在同一层叶子节点上。
- 其次，所有的叶子节点由指针连接。如下图为简化了的
B+Tree。
根据叶子节点的内容，索引类型分为主键索引和非主键索引。
- 聚簇索引（clustered）：又称为主键索引，其叶子节点存的是整行数据。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。InnoDB 的聚簇索引实际是在同一个结构中保存了 B 树的索引和数据行。
- 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary）。数据存储在一个位置，索引存储在另一个位置，索引中包含指向数据存储位置的指针。可以有多个，小于 249 个。
聚簇表示数据行和相邻的键值紧凑地存储在一起，因为数据紧凑，所以访问快。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。
聚簇索引和非聚簇索引的查询有什么区别
- 如果语句是
select * from T where ID=500，即聚簇索引查询方式，则只需要搜索 ID 这棵 B+ 树； - 如果语句是
select * from T where k=5，即非聚簇索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。
也就是说，基于非聚簇索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
显然，主键长度越小，非聚簇索引的叶子节点就越小，非聚簇索引占用的空间也就越小。
自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。从性能和存储空间方面考量，自增主键往往是更合理的选择。有没有什么场景适合用业务字段直接做主键的呢？还是有的。比如，有些业务的场景需求是这样的：
- 只有一个索引；
- 该索引必须是唯一索引。
由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。
内存是半导体元件。对于内存而言，只要给出了内存地址，我们就可以直接访问该地址取出数据。这个过程具有高效的随机访问特性，因此内存也叫随机访问存储器（Random Access Memory，即 RAM）。内存的访问速度很快，但是价格相对较昂贵，因此一般的计算机内存空间都相对较小。
而磁盘是机械器件。磁盘访问数据时，需要等磁盘盘片旋转到磁头下，才能读取相应的数据。尽管磁盘的旋转速度很快，但是和内存的随机访问相比，性能差距非常大。一般来说，如果是随机读写，会有 10 万到 100 万倍左右的差距。但如果是顺序访问大批量数据的话，磁盘的性能和内存就是一个数量级的。
磁盘的最小读写单位是扇区，较早期的磁盘一个扇区是 512 字节。随着磁盘技术的发展，目前常见的磁盘扇区是 4K 个字节。操作系统一次会读写多个扇区，所以操作系统的最小读写单位是块（Block），也叫作簇（Cluster）。当我们要从磁盘中读取一个数据时，操作系统会一次性将整个块都读出来。因此，对于大批量的顺序读写来说，磁盘的效率会比随机读写高许多。
假设有一个有序数组存储在硬盘中，如果它足够大，那么它会存储在多个块中。当我们要对这个数组使用二分查找时，需要先找到中间元素所在的块，将这个块从磁盘中读到内存里，然后在内存中进行二分查找。如果下一步要读的元素在其他块中，则需要再将相应块从磁盘中读入内存。直到查询结束，这个过程可能会多次访问磁盘。我们可以看到，这样的检索性能非常低。
由于磁盘相对于内存而言访问速度实在太慢，因此，对于磁盘上数据的高效检索，我们有一个极其重要的原则：对磁盘的访问次数要尽可能的少！
将索引和数据分离就是一种常见的设计思路。在数据频繁变化的场景中，有序数组并不是一个最好的选择，二叉检索树或者哈希表往往更有普适性。但是，哈希表由于缺乏范围检索的能力，在一些场合也不适用。因此，二叉检索树这种树形结构是许多常见检索系统的实施方案。
随着索引数据越来越大，直到无法完全加载到内存中，这是需要将索引数据也存入磁盘中。B+ 树给出了将树形索引的所有节点都存在磁盘上的高效检索方案。操作系统对磁盘数据的访问是以块为单位的。因此，如果我们想将树型索引的一个节点从磁盘中读出，即使该节点的数据量很小（比如说只有几个字节），但磁盘依然会将整个块的数据全部读出来，而不是只读这一小部分数据，这会让有效读取效率很低。B+ 树的一个关键设计，就是让一个节点的大小等于一个块的大小。节点内存储的数据，不是一个元素，而是一个可以装 m 个元素的有序数组。这样一来，我们就可以将磁盘一次读取的数据全部利用起来，使得读取效率最大化。
B+ 树还有另一个设计，就是将所有的节点分为内部节点和叶子节点。内部节点仅存储 key 和维持树形结构的指针，并不存储 key 对应的数据（无论是具体数据还是文件位置信息）。这样内部节点就能存储更多的索引数据，我们也就可以使用最少的内部节点，将所有数据组织起来了。而叶子节点仅存储 key 和对应数据，不存储维持树形结构的指针。通过这样的设计，B+ 树就能做到节点的空间利用率最大化。此外，B+ 树还将同一层的所有节点串成了有序的双向链表，这样一来，B+ 树就同时具备了良好的范围查询能力和灵活调整的能力了。
因此，B+ 树是一棵完全平衡的 m 阶多叉树。所谓的 m 阶，指的是每个节点最多有 m 个子节点，并且每个节点里都存了一个紧凑的可包含 m 个元素的数组。
即使是复杂的 B+ 树，我们将它拆解开来，其实也是由简单的数组、链表和树组成的，而且 B+ 树的检索过程其实也是二分查找。因此，如果 B+ 树完全加载在内存中的话，它的检索效率其实并不会比有序数组或者二叉检索树更 高，也还是二分查找的 log(n) 的效率。并且，它还比数组和二叉检索树更加复杂，还会带来额外的开销。
另外，这一节还有一个很重要的设计思想需要你掌握，那就是将索引和数据分离。通过这样的方式，我们能将索引的数组大小保持在一个较小的范围内，让它能加载在内存中。在许多大规模系统中，都是使用这个设计思想来精简索引的。而且，B+ 树的内部节点和叶子节点的区分，其实也是索引和数据分离的一次实践。
MySQL 中的 B+ 树实现其实有两种，一种是 MyISAM 引擎，另一种是 InnoDB 引擎。它们的核心区别就在于，数据和索引是否是分离的。
在 MyISAM 引擎中，B+ 树的叶子节点仅存储了数据的位置指针，这是一种索引和数据分离的设计方案，叫作非聚集索引。如果要保证 MyISAM 的数据一致性，那我们需要在表级别上进行加锁处理。
在 InnoDB 中，B+ 树的叶子节点直接存储了具体数据，这是一种索引和数据一体的方案。叫作聚集索引。由于数据直接就存在索引的叶子节点中，因此 InnoDB 不需要给全表加锁来保证一致性，它只需要支持行级的锁就可以了。
# LSM 树
B+ 树的数据都存储在叶子节点中，而叶子节点一般都存储在磁盘中。因此，每次插入的新数据都需要随机写入磁盘，而随机写入的性能非常慢。如果是一个日志系统，每秒钟要写入上千条甚至上万条数据，这样的磁盘操作代价会使得系统性能急剧下降，甚至无法使用。
操作系统对磁盘的读写是以块为单位的，我们能否以块为单位写入，而不是每次插入一个数据都要随机写入磁盘呢？这样是不是就可以大幅度减少写入操作了呢？解决方案就是：LSM 树（Log Structured Merge Trees）。
LSM 树就是根据这个思路设计了这样一个机制：当数据写入时，延迟写磁盘，将数据先存放在内存中的树里，进行常规的存储和查询。当内存中的树持续变大达到阈值时，再批量地以块为单位写入磁盘的树中。因此，LSM 树至少需要由两棵树组成，一棵是存储在内存中较小的 C0 树，另一棵是存储在磁盘中较大的 C1 树。
LSM 树具有以下 3 个特点：
- 将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并（Merge Trees）；
- 用批量写入代替随机写入，并且用预写日志 WAL 技术（Write AheadLog，预写日志技术）保证内存数据，在系统崩溃后可以被恢复；
- 数据采取类似日志追加写的方式写入（Log Structured）磁盘，以顺序写的方式提高写 入效率。
LSM 树的这些特点，使得它相对于 B+ 树，在写入性能上有大幅提升。所以，许多 NoSQL 系统都使用 LSM 树作为检索引擎，而且还对 LSM 树进行了优化以提升检索性能。
# 倒排索引
倒排索引的核心其实并不复杂，它的具体实现其实是哈希表，只是它不是将文档 ID 或者题目作为 key，而是反过来，通过将内容或者属性作为 key 来存储对应的文档列表，使得我们能在 O(1) 的时间代价内完成查询。
尽管原理并不复杂，但是倒排索引是许多检索引擎的核心。比如说，数据库的全文索引功能、搜索引擎的索引、广告引擎和推荐引擎，都使用了倒排索引技术来实现检索功能。
# 索引的维护
# 创建索引
- 数据压缩：一个是尽可能地将数据加载到内存中，因为内存的检索效率大大高于磁盘。那为了将数据更多地加载到内存中，索引压缩是一个重要的研究方向。
- 分支处理：另一个是将大数据集合拆成多个小数据集合来处理。这其实就是分布式系统的核心思想。
# 更新索引
（1）Double Buffer（双缓冲）机制
就是在内存中同时保存两份一样的索引，一个是索引 A，一个是索引 B。两个索引保持一个读、一个写，并且来回切换，最终完成高性能的索引更新。
优点：简单高效
缺点：达到一定数据量级后，会带来翻倍的内存开销，甚至有些索引存储在磁盘上的情况下，更是无法使用此机制。
（2）全量索引和增量索引
将新接收到的数据单独建立一个可以存在内存中的倒排索引，也就是增量索引。当查询发生的时候，我们会同时查询全量索引和增量索引，将合并的结果作为总的结果输出。
因为增量索引相对全量索引而言会小很多，内存资源消耗在可承受范围，所以我们可以使用 Double Buffer 机制 对增量索引进行索引更新。这样一来，增量索引就可以做到无锁访问。而全量索引本身就是只读的，也不需要加锁。因此，整个检索过程都可以做到无锁访问，也就提高了系统的检索效率。