1、二叉搜索树

每个节点只有两个子节点，数量多时会导致树的高度过高。

2、B树

• 关键字集合分布在整颗树中
• 任何一个关键字出现且只出现在一个结点中
• 搜索有可能在非叶子结点结束
• 其搜索性能等价于在关键字全集内做一次二分查找
• 自动层次控制

B树的查找，对单个值的查找，就是按照范围从上到下进行比较，最少一次磁盘IO，最多就是3次。
但如果是范围查找，就比较麻烦，需要不断地做中序遍历，磁盘IO次数会很多。

3、B+树

• 所有关键字都出现在叶子结点的链表中，且链表中的关键字是有序的
• 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
• 更适合文件索引系统

3.1、 B+树的搜索过程

B+树的查找，单个值的查找就是固定的等于树的高度。
范围搜索，找到最小值之后按照叶子节点的指针向后找到最后一个就可以了。