树的概念

树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构

树的分类

上图是树的分类图谱，我们常用的树有B树，B+树，二叉树，红黑树等

B树（B-）

B树是一种自平衡的多路搜索树，它可以有多个子节点。B树特别适合用于读写相对较大的数据块的存储系统，如磁盘

这里的 B 是 Balance（平衡）的缩写。它是一种多路的平衡搜索树。B树的每个节点可以存储多个数据，而且每个节点不止有两个子节点，最多可以有上千个子节点。B树中每个节点都存放着索引和数据，数据遍布整个树结构，搜索可能在非叶子节点结束，最好的情况是O(1)。一般一棵 B 树的高度在 3 层左右，3 层就可满足 百万级别的数据量

优点

减少了磁盘I/O操作。
保持了树的平衡。
对于大型数据集的查找和顺序访问非常高效。

缺点

节点分裂和合并的过程相对复杂。
当数据经常插入和删除时，维护成本较高。

应用

文件系统

B+树

B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于:

所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data) 为所有叶子结点增加了一个链指针

由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，叶子节点包含了全部数据，并且按左小右大顺序排列，B+ 树使用一个链表将它们排列起来，这样在查询时效率更快。也就是说同样数据情况下，B+ 树会 B 树更加“矮胖”，因此查询效率更快。但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

B树在提高了IO性能的同时并没有解决元素遍历效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

相比B-树，B+树的父节点也必须存在于子节点中，是其中最大或者最小元素，B+树的节点只存储索引key值，具体信息的地址存在于叶子节点的地址中。这就使以页为单位的索引中可以存放更多的节点。减少更多的I/O支出。因此，B+树成为了数据库比较优秀的数据结构，MySQL中MyIsAM和InnoDB都是采用的B+树结构。不同的是前者是非聚集索引，后者主键是聚集索引，所谓聚集索引是物理地址连续存放的索引，在取区间的时候，查找速度非常快，但同样的，插入的速度也会受到影响而降低。聚集索引的物理位置使用链表来进行存储。

优点

层级更低，IO 次数更少
每次都需要查询到叶子节点，查询性能稳定
叶子节点形成有序链表，范围查询方便

缺点

主要缺点包括产生大量的随机IO、占用更多空间、以及查询速度较慢。

产生大量的随机IO：B+树最大的性能问题在于会产生大量的随机IO，主要存在于两种情况：一是当主键不是有序递增时，每次插入数据会产生大量的数据迁移和空间碎片；二是即使主键是有序递增的，大量写请求的分布仍是随机的。

占用更多空间：由于B+树中键会重复出现，因此会占用更多的空间。尽管与带来的性能优势相比，空间劣势往往可以接受，但这一缺点仍然存在。

查询速度较慢：相对于Hash索引，B+树索引的查询速度较慢，平均时间复杂度为O(logN)。这表明B+树在查询效率方面不如Hash索引

应用

数据库索引。