B-Tree、B+Tree以及Hash

数据结构定义

m阶的定义

m是指树中结点可以拥有的最多孩子数量
1阶：任一结点最多拥有一个孩子结点
3阶：任一结点最多拥有三个孩子结点

m阶B-Tree的定义

1. 根结点的孩子数量：[2,m]
2. 非根结点的孩子数量：[,m]
3. 叶子结点都同一级，且均为null（严老师）
4. 结点的结构
   1. 关键字个数n：该结点的关键字数量
   2. 关键字：n个关键字
   3. 指针：n+1个子结点指针

1. 关键字数据中已经记录了真实数据的指针或数据。同一个关键字出现后就不会再次出现

   m阶B+Tree的定义

2. 根结点的孩子数量：[2,m]（同B-Tree）

3. 非根结点的孩子数量：[,m]（同B-Tree）
4. 叶子节点记录全部的关键字，且按照顺序依次连接
5. 结点的结构
   1. 关键字个数n：该结点的关键字数量
   2. 关键字：n个关键字
   3. 指针：n个子结点指针

1. 非叶子结点的关键字数据中只记录关键字，没有记录的指针或数据，只有叶子节点中有

   为什么MySQL使用B+Tree

   B-Tree

   优点

2. 查询单条记录，只要在结点中检索到关键字就可以立即返回，无需到叶子节点。可以将高频的数据放在靠近根结点的层级上，可以更快的查到。

   缺点

3. 范围查询时，B-Tree需要加载不同的层级去寻找数据

4. 由于非叶子结点中也存储了关键字对应的数据，导致数据占用关键字的存放空间。使得每页的关键字会更少一点。降低检索速度。

   B+Tree

   优点

5. 范围查询时，B+Tree只需要寻找叶子节点那层即可遍历出符合条件的所有数据

6. 非叶子结点不存储数据，关键字放置的就会多一点，加快检索速度

   缺点

7. 单条数据查询时，可能没有B-Tree快，因为均需要加载到叶子结点

   小结

   使用数据库查询的时候，较多的场景还是范围查询，B-Tree的范围查询效率实在太差。B+Tree的话虽然单条记录的查询速度略逊于B-Tree，但是也差不了太多。综合考虑下，还是使用B+Tree更好。

   MySQL不同引擎的索引数据结构

8. MyISAM

   1. 不支持Hash
   2. 支持B+Tree
9. InnoDB
   1. 不支持Hash
   2. 支持B+Tree

10. Memory

    1. 支持B+Tree
    2. 默认Hash

       InnoDB和MyISAM对B+Tree实现区别

11. InnoDB的聚簇索引存储的就是数据，MyISAM的聚簇索引依旧要回表

12. InnoDB的回表是拿着主键取聚簇索引查，MyISAM的回表都是拿着数据指针去查（更快）
13. InnoDB必须有主键，没有则选择一个唯一非空的键或者使用隐藏整数列

Hash和B+Tree

1. Hash查询单条记录很快，但是都要回表，范围查询比B-Tree还拉胯
2. B+Tree查询单条记录性能差，但是不一定都要回表，范围查询完胜Hash和B-Tree