数据库索引的总结

索引就是为了能快速查找到对应的数据，大学里肯定学过hash表这种key-value形式的查找结构。mysql的b+树索引也是key-value形式的查找结构，只是它还对key进行了排序像红黑树一样，而且能适应磁盘这种block存储的速度慢吞吐量大的特性。

从线性表的二分查找说起

线性查找是最野蛮的查找算法，最坏的情况从头遍历到尾，最好的情况比较一次，平均时间复杂度为N/2。

而二分查找能达到O(logN)的时间复杂度，但是前提是列表中的数据必须是有序的。

排序的时间复杂度O(NlogN)，还不如直接暴力线性查找的O(N)呢。

这个时候我们的二分查找树登场了。

用二分查找树优化二分查找

二分查找树(BST)基于二叉树的结构，添加了一个有序的规则：

• 左子树的值都小于父节点
• 右子树的值都大于等于父节点

用了二分查找树保存数据，就能让我们的增删改查都保持O(logN)的理论值了。这是我们用空间换时间的第一次实践。

不过这里提到是”理论值”，现实与理想还是很有差距的。因为二分查找树并不一定会按照我们的想法进行编排，它有致命的缺点：可能退化成链表

为了防止它退化，我们还需要给这个二分查找树加一些约束规则，让它的左右子树平衡一点。

这个时候平衡二叉树隆重登场。

平衡二叉树：AVL与RB树

我们给二分查找树加平衡规则：左右子树的高度差不能大于一。

我们可以把这个高度差定义为平衡因子(balance factor)，方便打字后面简写成BF。

每个节点都存储这么一个BF，BF的取值可以为-1，0，1。当我们插入一个新元素的时候，都会落在叶子节点上，从这个新节点回溯父节点重新计算BF，当出现-2或者2的时候说明左右子树不平衡了。需要我们对树进行旋转调整。

这棵平衡二叉树有个名字叫AVL树，是为了纪念发明这棵树的两位计算机科学先驱。

不过AVL有些缺点：因为要保证左右子树的严格平衡，增删操作需要回溯父节点而且可能需要经过一次或多次旋转。

在插入删除操作频繁的时候，效率相对比较低下；查找操作密集的场景下，AVL树就比较适用。

所以有另一个大牛发明了大名鼎鼎的”红黑树(Red-Black)”改良这个平衡规则：

• 每个节点要么是红色要么是黑色
• 根节点是黑色
• 所有叶子(NULL LEAF,空节点)都是黑色的
• 如果一个节点是红色的，那么它的两个子节点都是黑色的
• 从给定节点到其后代任何一个NIL节点的路径都包含相同数量的黑色节点

根据这几个特性知道：从根到最远的叶子节点的路径不超过从根到最近叶子节点路径的两倍。红黑树大致上高度平衡，并不像AVL树那样严格平衡。红黑树整体增删改查效率会更好一点。

各个语言的标准库里都有这个数据结构了，一般不用我们自己写代码实现。

磁盘中的平衡树：B树

平衡二叉树在内存里面增删改查数据能保证O(logN)的时间复杂度。但是数据量超过内存咋办呢。对于这种大数据量的查找，我们需要用到专门针对磁盘进行优化的数据结构了。这个最典型的就是B树。

树这种数据结构每个节点空间一般都是临时分配的，也就是说每个节点存储的物理位置都是随机的。如果我们把红黑树存在磁盘里，会怎样呢? 每次访问一个节点都可能造成一次随机的磁盘IO。

磁盘的特性是读写很慢，而且每一次读写以一个扇区块为单位。

红黑树这种二叉查找树，数据量一大，树的深度越大，随机的磁盘IO次数越多，这将会严重降低二叉搜索树的效率。

B树就是用来优化这个问题的，B树每个节点可以存m个元素，根据这m个元素可以划分m+1个区间，也就有了m+1个子节点。B树有一个平衡规则：

• 根结点至少有两个子节点。
• 节点元素个数应该在[m/2,m]这个区间内，元素太少需要合并节点，元素太多需要分裂。

同样多的数据，在红黑树中是棵高高的树，到了B树中就变成了又矮又胖的树了。

为了简单起见，以m=3的2-3Tree为例。插入数据时，当节点中的数据达到3个，就会发生分裂：中间的值将会升级成父节点，比中间值小的将分裂成左子节点，比中间值大的将分裂成右子节点。

一般我们的B树节点占的空间是磁盘的扇区块的整数倍。比如MySQL的InnoDB存储引擎默认是16KB页大小，是新型磁盘扇区的4倍。

我们算一下16KB的页，当，根节点大概有500个元素。

根节点下的1层树能存储的数据。

2层树能存储的数据。

3层树能存储的数据。

4层树能存储的数据

……

m具体取值多少呢，一般取决于我们的元素占用多少空间。B树是将Key-Value键值对作为元素存储的查找结构，为了让m更大一点，让每个节点存储更多的元素。B+树被发明出来了。

1、B+树内部的非叶子节点只存储Key，用来索引，不保存Value数据，所有的Value数据都保存在叶子节点中

非叶子节点只存储Key，对于同样大小的节点来说，可以让节点存储更多的Key，这变相地降低了树的深度，从而让B树索引更多数据。
同时对内存的索引缓存更友好，内存中就能缓存更多层级的数据了。
所有的查找最终都会查找到叶子节点，也保证了查询性能的稳定。

2、B+树叶子节点之间用指针串联起来，方便范围查询

因为B树进行范围查询时需要回溯，对于硬盘中的数据结构而言，一次回溯意味着一次随机磁盘IO。

了解了B+树的原理，你就了解了市面上大部分数据库的存储原理了。接下来就是不同的数据库怎么应用这个B+树了。

聚簇索引与非聚簇索引

目前数据库B+树索引有两种用法：聚簇索引与非聚簇索引

比如MySQL的MyISAM引擎就是非聚簇索引，MyISAM会把数据存在一个heap文件中(后缀名为.MYD)，创建的B+树索引存在另一个索引文件中(后缀名为.MYI)。

所有的B+树索引叶子结点存储的是数据在heap文件中的物理地址。

而MySQL的InnoDB引擎的主键索引就是聚簇索引，数据直接存在主键索引的叶子结点内，聚簇索引包含了整个表的完整数据。二级索引不再存储数据的物理地址，而是存储主键。

这两者有什么优缺点呢：

• 使用聚簇索引将会比非聚簇索引访问更快，因为聚簇索引将数据保存在同一个B+树中，通过索引就能查到数据；而非聚簇索引需要访问堆文件，多一次随机IO。

• 使用聚簇索引时，数据更新一般不会影响二级索引，只有当数据修改涉及到二级索引中的列时才需要更新二级索引；而使用非聚簇索引，堆文件中数据行物理地址更新了，需要更新所有的二级索引。

• 聚簇索引的数据按主键排序的，插入的速度回严重依赖于插入顺序，按照主键的顺序插入到聚簇索引时速度最快的。如果使用UUID这样的随机数据作为主键，插入会变成随机IO，严重影响插入性能，而且B+树叶节点数据分布不均，会导致占用更多的磁盘空间。

  如果导入数据不是按照主键顺序加载数据，那么加载完成后最好使用OPTIMIZE TABLE命令重新组织一下表。

• 使用聚簇索引的表在插入新行，或者主键被更新导致数据行需要移动时，可能面临“页分裂”的问题。当数据行插入已满的叶节点时，存储引擎需要将叶节点分裂成两个页面来容纳数据。也分裂会影响IO性能，占用更多更多的磁盘空间。

• 使用聚簇索引时，通过二级索引查找需要回主键索引再查一次B+树才能拿到完整的数据行；而非聚簇索引的二级索引和主键索引性能一样，可以直接访问堆文件中的数据行。

  使用聚簇索引时，可以通过索引覆盖查询来避免二级索引的回表查询。

• 使用聚簇索引时，索引可能比想象的更占空间，因为二级索引叶节点包含了引用行的主键列，所以最好是使用数值类型的单列作为索引，避免索引的数据量过大。

基于日志结构优化索引的写性能：LSM-Tree

面对更大的数据量，B+树的深度会加大，随机IO次数也会增多，所以通常有人说当单表数据量达到500W时，需要分库分表。

关于分库分表可以参考我的前一篇文章

另一方面，B+树是读性能优化的索引结构，特别是聚簇索引的用法，在写操作比较多的大数据场景，页分裂也会导致B+树的写入性能极其不稳定。

我们知道数据库通常会用日志来保证事务的原子性与持久性，日志的顺序IO能保证事务的性能不受影响。

而LSM-Tree(Log-Structure Merge Tree)也是使用日志结构的顺序IO来优化索引的写入性能。

• 插入的数据先存储在内存里的树，当它的大小达到一定阈值，将会刷入到磁盘中的树。由于内存读写速度普遍比外存快得多，所以树写入效率很高。当数据从内存刷入磁盘时树是预排序的，也就是说，LSM树将原本随机写操作转化成了顺序写操作，写性能大幅提升。

• 通常树可以使用红黑树等内存数据结构，…等树可以使用B树等磁盘存储结构。同样为了保证内存中数据的持久性，需要一个预写日志（Write-Ahead Log），每次写操作都会以顺序IO的形式写入日志以便数据库系统的崩溃恢复。

• 这里面除了内存中的树，其他写入到磁盘的…树都是不可变的。当磁盘中的树数量达到一定阈值，会有后台Merge线程会用类似于MergeSort的算法将多个树Merge成更大的树，同样当树数量达到一定阈值，也会Merge成更大的树… Merge的过程中会将相同key的老数据合并(compact)掉。

LSM-Tree的几个特点能极大的优化索引的写入速度，但是也带来了其他的问题：

• 读放大：原来B+树只需要读取一棵树，而LSM-Tree的读取需要从到依次遍历多棵树，读取次数被放大了。这也是为什么LSM-Tree需要一个后台线程对多个磁盘树进行Merge的原因。另外对于这个问题，还有一个常见的做法是使用BloomFilter，以少量的内存空间为代价，对数据的存在性进行预判，确定数据是否在磁盘中的树中，可以适当地减少磁盘的读取次数。
• 写放大：原来B+树每次写入通常就地修改，只是页分裂的时候才会导致写入速度的降低，而且一般数据库会将B+树内存的脏页定时刷新来优化写入性能，用redo-log的立即写保证数据的持久性。而LSM-Tree，不仅仅写入磁盘时会消耗磁盘带宽，后台Merge线程负责将多个树compact成一个树，Merge次数越多，原数据被重新写到磁盘的次数也就越多，写入次数被放大了。
• 空间放大：由于LSM-Tree在磁盘中的树是不可变的，修改操作将会导致数据在LSM-Tree中存储多个版本，修改次数越多，占用空间越多，空间被放大了。只有当后台的Merge线程compact的时候，才会清理历史数据。

这三者的带来的影响与Merge线程compact算法息息相关。具体可以参考一文带你了解LSM Compaction。

目前LSM-Tree在现代很多数据库中都有使用，如谷歌的BigTable和Hadoop的开源实现HBase，以及MongoDB的WiredTiger引擎。

另外google/LevelDB与facebook/RocksDB是被广泛使用的LSM-Tree存储库，如TiDB的存储引擎TiKV就是基于RocksDB构建的，MySQL的LSM-Tree实现MyRocks引擎也是基于RocksDB构建的，包括阿里的X-DB等。