B树B+树

BST树 (二叉排序树)

1. 根节点的值大于其左子树中任意一个节点的值
2. 根结点的值小于其右节点中任意一节点的值
3. 这一规则适用于二叉查找树中的每一个节点 优点：查询的时间复杂度比链表快，链表的查询时间复杂度是O(n)，二叉排序树平均是O(logn) 缺点：如果插入的结点的值的顺序，是越来越小或者越来越大的，那么BST就会退化为一条链表，那么其查询的时间复杂度就会降为O(n)

AVL树 (平衡二叉树)

1. 拥有BST树的特点
2. AVL树上任意结点的左、右子树的高度差最大为1

B树(平衡多路查找树) B树的阶数：M阶表示 一个B树的结最多有多少个查找路径(即这个结点有多少个子节点)。M=M路，M=2是二叉树，M=3则是三叉树 1.每个结点的值(索引) 都是按递增次序排列存放的，并遵循左小右大原则。

2. 根结点 的子节点 个数为 [2，M]。
3. 除 根结点 以外 的 非叶子结点 的子节点个数 为[ Math.ceil(M/2)，M]。 Math.ceil() 为向上取整。
4. 每个非叶子结点 的值(索引)个数=子节点个数 -1,最小为 Math.ceil(M/2)-1,最大为 M-1 个。
5. B树的所有叶子结点都位于同一层。

B+树 B+树内部有两种结点，一种是索引结点，一种是叶子结点。 B+树的索引结点并不会保存记录，只用于索引，所有的数据都保存在B+树的叶子结点中。而B树则是所有结点都会保存数据。 B+树的叶子结点都会被连成一条链表。叶子本身按索引值的大小从小到大进行排序。即这条链表是 从小到大的。多了条链表方便范围查找数据。 B树的所有索引值是不会重复的，而B+树 非叶子结点的索引值 最终一定会全部出现在 叶子结点中。

B树好处： B树的每一个结点都包含key(索引值) 和 value(对应数据)，因此方位离根结点近的元素会更快速。（相对于B+树） B树的不足： 不利于范围查找(区间查找)，如果要找 0~100的索引值，那么B树需要多次从根结点开始逐个查找。 而B+树由于叶子结点都有链表，且链表是以从小到大的顺序排好序的，因此可以直接通过遍历链表实现范围查找。

参考原文链接：https://blog.csdn.net/u014453898/article/details/112469113