本文将介绍 B+ 树，它常用于数据库系统和文件系统中。

一、二叉排序树

二叉排序树在插入节点时，会根据 “左 < 根 < 右” 的规则，将新节点插入到合适的位置。

二叉排序树提供了一种通过树形结构快速定位数据的可能。

二、平衡二叉树

平衡二叉树是对二叉排序树的改进，在二叉排序树的基础上，额外限制了左右子树的高度差距。

平衡二叉树避免了树不平衡时，查询效率由 o(logn) 退化为 o(n) 的可能。

三、B 树

B 树，即 Balance Tree，平衡树。与平衡二叉树相比，它的子节点数不再被局限为 2，因此又被称为平衡多路查找树。

四、B+ 树

B+ 树是对 B 树的改进，主要在两个方面：数据只存储在叶子节点上、所有的叶子节点通过一个链表连接。

B+ 树的优点是：

• 层级更少

  在 B 树中，数据会存在非叶节点的元素中，因此元素大小肯定会增加。假设节点容量固定，与 B+ 树相比，B 树中能够存储的元素数量势必更小，这将导致 B 树层级更高。

• 查询速度更稳定

  B 树的数据可能存在非叶节点中，更近的数据将会更快被找到。

  B+ 树的数据都在底部，因此每次查询所需的时间都大致相等。

• 查询区间数据更方便

  由于 B+ 树有链表，因此在查询 “相邻数据” 时更方便

• 遍历更方便

  由于 B+ 树有链表，因此可以通过链表更方便地遍历所有数据