Jovry's blog
0%

MySQL-为什么使用B+树作为索引结构

Posted on Edited on In

1 概述

首先，MySQL和B+树是没有直接关系的，真正与B+树有关系的是MySQL的默认存储引擎InnoDB，MySQL中存储引擎的主要作用是负责数据的存储和提取．除了InnoDB外，MySQL还支持另外一些存储引擎，例如，MyISAM．使用show engines命令可查看．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mysql> show engines;
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| Engine             | Support | Comment                                                        | Transactions | XA   | Savepoints |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| MyISAM             | YES     | MyISAM storage engine                                          | NO           | NO   | NO         |
| MRG_MYISAM         | YES     | Collection of identical MyISAM tables                          | NO           | NO   | NO         |
| InnoDB             | DEFAULT | Supports transactions, row-level locking, and foreign keys     | YES          | YES  | YES        |
| BLACKHOLE          | YES     | /dev/null storage engine (anything you write to it disappears) | NO           | NO   | NO         |
| PERFORMANCE_SCHEMA | YES     | Performance Schema                                             | NO           | NO   | NO         |
| CSV                | YES     | CSV storage engine                                             | NO           | NO   | NO         |
| ARCHIVE            | YES     | Archive storage engine                                         | NO           | NO   | NO         |
| MEMORY             | YES     | Hash based, stored in memory, useful for temporary tables      | NO           | NO   | NO         |
| FEDERATED          | NO      | Federated MySQL storage engine                                 | NULL         | NULL | NULL       |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
9 rows in set (0.24 sec)

对于InnoDB来说，所有数据都是以键值对的方式存储在Ｂ+树结构中，其中表中的数据（主键索引）以<id, row>的方式存储；而辅助索引以<index, id>的方式进行存储．

  • 在主键索引中，ｉｄ是主键，通过ｉｄ能找到该行的全部列．
  • 在辅助索引中，索引中的几个列构成了键，通过索引中的列找到ｉｄ，如果有需要的话，可以再通过ｉｄ找到当前数据行的全部内容．

2 分析

MySQL作为OLTP(Online Tranaction Processing)的数据库，不仅需要具备事务的处理能力，还要保证数据的持久化并且能够有一定的实时数据查询能力．

一般来说索引文件本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上．这样的话，索引查找过程就会产生磁盘I/O消耗，相对于内存的存取，I/Ｏ存取的消耗要高几个数量级，所以评判一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂读．换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数．

对于普通磁盘（非ＳＳＤ）加载数据需要经过队列，寻道，旋转以及传输这些过程，大约耗时为１０ｍｓ左右，如下图所示：

磁盘IO消耗

对于InnoDB选择B+树索引结构原因可以从以下几个方面进行分析：

  • 考虑其支持的场景和功能需要在特定查询上拥有较强的性能；
  • CPU将磁盘上的数据加载到内存需要花费大量的时间，采用Ｂ+树将是非常好的选择；

2.1 读写性能分析

这里选取哈希结构及Ｂ树结构进行对比分析．

2.1.1 与哈希结构进行比较

  • 若使用Ｂ+树作为底层的数据结构，其增删改查一条数据的ＳＱＬ的时间复杂度都是O(lg n)，即树的高度．

  • 若使用哈希作为底层的数据结构，其增删改查一条数据的ＳＱＬ的时间复杂度可能达到Ｏ(1)．

  • 对于单行数据的读写，哈希索引均比Tree型索引块，但是对于某些特殊的查询SQL，例如分组、排序、比较等情况，哈希索引的时间复杂度会退化为O(n)，而Tree索引因为其有序的特性，能依旧保持O(lg(n))的高效率。

2.1.2 与Ｂ树进行比较

Ｂ树和Ｂ+树在数据结构上起始有一些相似的，都能按照某些顺序对索引中内容进行遍历，排序及范围查找，相比哈希结构来说，Ｂ树和Ｂ+树能带来更好的性能．

2.2 数据加载

哈希结构无法满足一些特殊的查询SQL，而Ｂ树和Ｂ+树均能相对高效的执行，那么为什么不选择Ｂ树呢？

Ｂ树与Ｂ+树最大的区别就是，Ｂ树的非页结点中可以存储数据，但是Ｂ+树所有数据都是存储于叶子结点中．

2.2.1 B树数据加载分析

当一个表的底层数据结构是Ｂ树时，假设我们需要访问索引在［4, 9］区间的数据：

b-tree

在不考虑优化的情况下，在上面简单Ｂ树中需要进行４次磁盘的随机I/O访问才能找到所有满足条件的行：

  • 加载根结点所在的页，发现根结点的第一个元素是６，大于４；
  • 通过根节点的指针加载左字节点所在的页，遍历页面中的数据，找到５；
  • 重新加载根节点所在的页，发现根节点不包含第二个元素；
  • 通过根节点的指针加载右子节点所在的页，遍历页面中的数据，找到７，８；

（以上过程不考虑对过程进行优化，Ｂ树能做的优化Ｂ＋树都能做）

由上述过程可见，对于Ｂ树，由于所有结点都可能包含目标数据，总是需要从根结点向下遍历子树查找满足条件的数据行，这个特点带来了大量的随机I/O，这就是Ｂ树最大的性能问题．

2.2.2 B+树数据加载分析

对于B+树，由于其数据行均存储在叶子结点中，而这些叶节点可以通过指针依次顺序连接，如下图所示．当需要遍历数据时，可以直接在多个子节点之间通过指针跳转，这样可以节省大量的磁盘I/O时间，也不需要在不同层级的节点之间对数据进行拼接和排序．通过一个 B+ 树最左侧的叶子节点，可以像链表一样遍历整个树中的全部数据，也可以引入双向链表保证倒序遍历时的性能。

mysql-innodb-b-plus-tree

Ｂ+树的所有数据仅存储于叶子节点中，会不会导致树的高度增加，从而影响耗时呢？

其实这个影响是可以忽略不计的，对于高度为３的Ｂ+树就能存储千万级别的数据量．可通过以下计算量化，并得出结论：

  • 根据局部性原理，将一个节点的大小设为一页，一页为４Ｋ，假设一个Key有８个字节，那么一个结点至少可以存储500个Key．
  • 根据Ｍ叉搜索树特性，非根节点包含的关键字个数需要满足[[m/2], m]区间，即Ｍ大约为1000叉．
  • 那么，可以知道：
    • ​ 一层：１个节点，1 * 500个key，大小为４ｋ；
    • ​ 二层：1000个节点，1000 * 500 = 50W个key，大小为1000 * 4k = 4M;
    • ​ 三层：1000 * 1000个节点，1000 * 1000 * 500 = 5亿个key，大小为1000 * 4M = 4G

即３层的Ｂ+树结构，可以存储的数据量大约在５亿左右，其中索引占据的内存大小为４Ｇ左右．

3 总结

任何不考虑应用场景的设计都不是好设计，在明确了解MySQL常见的应用场景之后，再对不同的数据结构进行选择就是理所当然的事了．当然Ｂ+树并不能对所有的OLTP场景下的查询都有着较好的性能，但是它能解决大部分的问题．

  • 与哈希结构做对比：哈希虽然能提供Ｏ(1)的单数据操作性能，但对于范围查询，分组，排序等功能却无法很好的支持，最终导致全表扫描；
  • 与Ｂ树结构作对比：Ｂ树能够在非叶子节点中存储数据，这将导致在查询连续数据时可能会带来更多的随机I/O，而Ｂ+树的所有叶节点可以通过指针相互连接，能够减少顺序遍历时产生的额外随机I/O；
  • 与红黑树结构作对比：红黑树结构的高明显要深很多，由于逻辑上很近的节点（父子结点）物理上可能很远，无法利用局部性原理，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比Ｂ树差很多．

B+Tree相比B-Tree有的优势包括：

  • ①、范围查找，定位min和max之后，中间叶子节点，就是结果集，不需要中序回溯；
  • ②、叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储。
  • ③、非叶子节点，不存储实际记录，而只存储记录的Key的话，那么在相同内存的情况下，B+Tree能够存储更多的索引。

数据库的索引最常用的是B+树的原因：

  • ①、很合适磁盘存储，能够充分利用局部性原理，磁盘预读；
  • ②、很低的树高度，能够存储大量数据；
  • ③、索引本身占用的内存很小；
  • ④、能够很好的支持单点查询、范围查询、有序性查询。

参考资料

1 为什么MySQL使用B+树

2 数据库索引，到底是什么做的？

3 为什么实用B-Tree（B+Tree）