MySQL 调优之树和索引

（调优课二 1:26:13 开始讲）

MySQL 是用 B+ 树来实现索引。

哈希表

哈希表就相当于一个散列表 map，取模运算得出下标位置。MySQL 的 Memory 搜索引擎用了哈希索引。

• 查等值而不是查范围
• 需要全部读入内存

二叉树

子结点最多有两个的树，就是二叉树。

BST 二叉搜索树

有顺序的二叉树，左边普遍小于父结点，右边普遍大于父结点。

• 会导致数据倾斜。
• 二叉树会让树节点过深，一次深度会有一次 IO

AVL 平衡树

为了保证整个树的平衡，插入数据时会对树进行旋转。
让各节点左子树和右子树高度的差值最大保持为 1。若在某节点上大于 1，则在此节点向小的位置下移。

效用：

• 损失了插入删除效率，保证查询性能。

RBT 红黑树

最长树不超过最短树的 2 倍。

旋转操作还在，增加了变色功能，减少旋转的次数

• 任何单分支中不会有 2 个连续的红色节点
• 每个分支中黑色节点的个数总是一致的
• 它在插入和查询之间达到一种平衡

但还是会有节点过深导致 IO 操作变多，所以问题不在于二叉的变形，而就在于二叉本身。

B 树

将分支变多，每个磁盘块，一般默认 16 k（可设置）为 1 页的数据块，一次读取为 1 页。

如下图，B 树中存的数据是存有数据 data 的，所以每个数据块（也就是每页）只能存 16k 的数据。假设一条 MySQL 记录是 1k 的话，一页就只能存 16 条数据，三层的树最多能存 16^3=4096 条数据。

问题：大部分磁盘空间被 data 占用。

B 树

B+ 树

在 B 树上做了优化，在树干上只存节点信息，而不存数据块，将数据块存于叶子节点中。

假设一条记录的关键值为 10 个字节，那一页就可以存 1600 条数值，那三层总共就可以存 1600^3 个数值，即能检索 4096×10^6 个条目。

注意：这里存的是关键值了，而没有数据条目了。

一般 三层 就可以支持千万级别的数据的查询， MySQL 会自动调整层数。

image.png

B+ 树还做了优化，叶子节点的数据块也是相互连接的，可以进行顺序扫描。

B* 树

B* 树在 B+ 树的基础上，让非叶子节点数据块也相连了

B*树

InnoDB 搜索引擎和 MyISAM 搜索引擎的不同

他们都用了 B+ 树，但区别如下：

• InnoDB 中叶子节点每个数据值对应得存储就是对应条目的数据
• MyISAM 中叶子节点中存储的是对应条目的地址

问：MySQL查询效率到底快不快

影响因素：

• IO 次数
• 并发，并发时需要频繁得读数据到内存并进行替换，所以变慢

索引用的专业名词

索引的创建有考虑两点：一是查询效率；二是索引本身占用的空间大小。

回表

InnoDB 默认为主键创建索引，但当你用一个普通列创建索引时，如 Name，它最后的叶子并不是整行数据，而是主键。这时它的查询方式就是先按 Name 索引查到主键，然后再根据主键索引查到数据，经历了第二次查询就是回表。

覆盖索引

还是上面回表的例子，若你用 select name from xxx 即查出的字段完全是索引中的字段，这样的话就只需要查第一个索引就可以返回，而不用再用 ID 去查，这时就是覆盖索引。

比如有索引 a_1_b_1_c_1，当你用 select a, b from xxx where a = 1 and b = 2 and c = 3 时，就是覆盖索引。a, b 换成 a, b, id 也是覆盖索引，因为 id 是索引的 B+ 树中的叶子节点。

最左匹配

就是MongoDB中提到的前缀匹配。

where 语句的匹配。如现在创建索引字段为 name, age，当你查 where name = ? and age = ? 时就是最左匹配，但只查 age = ? 跳过了 name 就不是最左匹配了。

上面例子的解决方案：

• 建索引时将 age 放在 name 前
• 新增一个索引 age

索引下推

索引的查找，第一个字段是 range 类型，第二个索引字段为直接匹配的时候，第二个索引字段直接下移到搜索引擎，而以前是在MySQL的Server上做的筛选。

如，有一个索引 (name, age)，并且搜索 name=张% and age=10。

• 以前搜索的时候按 name 指定的范围从索引引擎中查出数据，而后在 Server 层对 age 进行筛选。
• 后来检索的时候直接在搜索引擎中按 name, age 的 age 进行一次筛选，再进 Server 层，这样就更快。

这就是索引下推

索引合并

页分裂和页合并

MongoDB

MongoDB 用的是 B 树，而 MySQL 用的是 B+ 树。

先比较特点：

• B 树数据块上存有 data，所以查单一数据最快是 O(1) 的复杂度；而 B+ 树总需要三次；
• B+ 树叶子是相连的，所以很适合做范围查询。

它们的区别正是由于非关系型数据库和关系型数据库不同导致的。
关系型数据库的一个明显特点就是可以用 join 连接表，这个时候常常用到遍历数据，所以用 B+ 树更优。
而非关系型数据库中存的是文档，它更常用的是单点查询，所以用 B 树更合适。