二叉树：
顾名思义，就是一个节点分出两个节点，称其为左右子节点；每个子节点又可以分出两个子节点，这样递归分叉，其形状很像一颗倒着的树。
二叉树限制了每个节点最多有两个子节点，没有子节点的节点称为叶子
完全二叉树：除了最高层以外，其余层节点个数都达到最大值，并且最高层节点都优先集中在最左边。
满二叉树：除了最高层有叶子节点，其余层无叶子，并且非叶子节点都有2个子节点。满二叉树必然是一个完全二叉树。
二叉查找树：左子树的键值小于根的键值，右子树的键值大于根的键值。
平衡二叉树：在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1
平衡多路查找树：
- 系统从磁盘读数据到内存是以磁盘块 block 为单位的，一次读一整块。
- InnoDB 存储引擎中有页 page 的概念，是磁盘管理的最小单位。默认每个页的大小是16k。
- 预读：所以每次查询的时候都会申请若干地址连续的磁盘块来达到16k 的大小。
- 如果一个页的每条数据都能有助于定位数据记录的位置，这将会减少磁盘 IO 次数，提高查询效率。
B-Tree是一种多路自平衡搜索树。和二叉树的区别在于，他允许每个节点有更多的子节点。
m 阶B-Tree特点：
- 所有键值分布在整个树中
- 任何关键字出现且只出现在一个节点中
- 搜索有可能在非叶子节点结束
- 在关键字全集内做一次查找，性能逼近二分查找算法
- 每个节点最多拥有m个子树
- 根节点至少有2个子树
- 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
- 所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列
B+Tree是 B-Tree 的变体，也是一种多路平衡查找树
他和 B-Tree 的区别在于：
1.所有关键字存储在叶子节点，非叶子节点只存储 key 信息
2.为所有叶子节点增加了一个链指针
在 MySQL 中，InnoDB 引擎存储索引使用的就是 B+Tree。
- 因为 MySQL 是基于磁盘的数据库，索引是以文件形式存在磁盘里的。索引查找的过程就会涉及到磁盘 IO。磁盘 IO 的消耗比内存 IO 的消耗高了好几个数量级，所以索引的数据结构要在查找的时候能够尽可能的减少 IO 的次数。
-
由于 B+Tree 的内节点不存储数据，所以每个内节点可以存储更大范围的 key，也就是每次 IO 的效率比 B-Tree 高。
-
B-Tree 由于每个节点都有 key 和 data，所以不支持范围查询。而 B+Tree 的叶子节点间按照顺序建立了链指针，加强了区间访问性，对范围查询比较友好。
InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。
- 简单的来说，B+Tree 的优点就是因为只存储 key，所以每一层能够存储的 key 更多，需要 IO 的次数就越少
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2\~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。
数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。