@TOC
1.树的基本概念
树的特点：有一个树根，树根上又有很多枝干，枝干上又有很多树枝，树枝上又有很多叶子
树最为一种数据结构也有相似特点
树是一个有限集合
根节点：有且只有一个特定的根节点，
节点：包含数据元素和若干指向其子树的分支
父节点、子节点、兄弟节点
一棵树可以没有任何节点，称为空树
一棵树可以只有 1 个节点，也就是只有根节点
子树、左子树、右子树
节点的度（degree）：子树的个数
树的度：所有节点度中的最大值
叶子节点（leaf）：度为 0 的节点
非叶子节点：度不为 0 的节点
层数（level）：根节点在第 1 层，根节点的子节点在第 2 层，以此类推（有些教程也从第 0 层开始计算）
节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数
节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数
树的深度：所有节点深度中的最大值
树的高度：所有节点高度中的最大值
树的结构是递归的
2.二叉树
二叉树是树形结构的一个重要类型，也是众多数据结构的基石。
每个节点最多只能有两个子节点的叫二叉树。
所以，二叉树的特性就是每个节点的子结点不允许超过两个
特殊类型
1、满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树 。
2、完全二叉树：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树 [4] 。
完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1 [4] 。
3.b树
B树:（也叫B-树，一部分人会习惯上把B-树读为B减树，其实并不存在B减树，只是读法上的不同而已）
维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。
B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。”
B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点
4.b+树
B+树是应文件系统所需而产生的B树的变形树
B+树的定义
一颗m阶的B+树满足如下条件：
每个节点最多只有m个子节点。
除根节点外，每个非叶子节点具有至少有 m/2（向下取整）个子节点。
非叶子节点的根节点至少有两个子节点。
有k颗子树的非叶节点有k个键，键按照递增顺序排列。
叶节点都在同一层中。
5.b树与b+树的对比
1.B+ 树非叶子节点上是不存储数据的，仅存储键值，而 B 树节点中不仅存储键值，也会存储数据。
之所以这么做是因为在数据库中页的大小是固定的，InnoDB 中页的默认大小是 16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。另外，B+ 树的阶数是等于键值的数量的，如果我们的 B+ 树一个节点可以存储 1000 个键值，那么 3 层 B+ 树可以存储 1000×1000×1000=10 亿个数据。
一般根节点是常驻内存的，所以一般我们查找 10 亿数据，只需要 2 次磁盘 IO。2.B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。
那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而 B 树因为数据分散在各个节点，要实现这一点是很不容易的。
因此，存在大量范围查询的场景，适合使用B+树（比如数据库）；
而对大量单个key查询的场景，可以考虑B树（比如NOSQL的MongoDB）
5.MySQL索引底层数据结构
MySQL索引的底层数据结构是B+树数据结构
B+树有三个特性
1、B+树是一个平衡多叉树，与平衡二叉树的每一个节点下面最多有两个子节点相比B+树每一个节点下面有多个子节点。
2、B+树叶子节点（也就是最下面一层的没有子节点的节点）有一个双向链表，左右是为了方便范围查找（假如我找前100条数据，那么我找到第一条叶子节点的数据就可以从叶子节点直接向后取100个数据即可，不用再从根节点向下寻找）
3、B+树的叶子节点有data数据（就是数据库中这一条所有的字段数据），非叶子节点只有索引数据。
为什么MySQL底层使用B+树而不使用B树呢
B树与B+树有两个地方不同，一个是叶子节点的双向链表，一个是B树不是只有叶子节点有data数据，而是所有的节点都有data数据。
之所以B+树要把其他节点的data数据去掉，只留叶子节点的data数据是因为涉及到计算机中的IO操作，计算机IO一次只能拿一数据页的数据，如果每一个节点都有data数据，那么计算机IO一次可能只够拿一个节点出来，这样，可能IO一百次才能找到结果，如果其他节点不存储data数据，那么这个索引占用空间就少，IO一个可以拿出多个节点来，这样IO的次数就大大降低了，IO一次是比较耗费性能的，所以使用B+树就提高了性能。
