（调优课二 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 树更合适。
网友评论