二叉排序树或平衡二叉树（AVL树、红黑树）

查找-之二叉排序树（查找、插入、删除）

查找-之平衡二叉树AVL和红黑树

结点只有两个孩子，且结点只能存储一个元素

问题：

一个结点只存储1个元素，在元素很多时，使得树的深度或高度很大

    出现的问题是：内存存取外存的次数非常多-使得时间效率降低

解决方法：

2-3树

结构：

1970年 约翰·霍普克洛夫发明的多路查找树，它一个结点具有2孩子（2结点）或3孩子（3结点）

2结点：一个元素+2个孩子（或没有孩子）

3结点：一大一小2元素+3个孩子（或没有孩子），3个孩子的排列顺序是小、中、大

2-3树结构图

2-3-4树

结点具有2孩子（2结点）或3孩子（3结点）或4个孩子（4结点）

结构：

2结点：一个元素+2个孩子（或没有孩子）

3结点：一大一小2元素+3个孩子（或没有孩子），3个孩子的排列顺序是小、中、大

4结点：小中大3元素+4个孩子（或没有孩子），  4个孩子的排列顺序是小、中、大

B树

Blance-Tree

一种平衡多路查找树，其中的2-3树和2-3-4树是B树的特例，结点最大的孩子数目称为B树的阶，

B树的孩子数目有可以有多个

其中：

2-3树最多有3个孩子--3阶B树

2-3-4树最多有4个孩子--4阶B树

B树是如何做到减少内存和外存数据交换的次数？

    在处理的硬盘数据量很大，一次无法全部装入内存--调整B树的阶数和硬盘存储的页面大小匹配，让树的根结点持久保存在内存中；例如：B树的阶为1001，则一个结点包含1000个关键字，高度为2，可以存储10亿个关键字，那么在这棵树上寻找关键字至多需要两次硬盘的读取。

B树减少定位记录时所经历的中间过程，从而加快存取速度

适用于：内外存数据的交互、 读写相对大的数据块的存储系统、文件系统的查找、数据库索引

时间复杂度：O（logn）

缺点是：B树需要中序遍历结点，且最坏的情况是在叶子结点找到

B+树

在出现分支结点中的元素会被当做该分支结点位置的中序后继者（叶子结点）再次列出

                                  B+树的存储结构

和B树的区别：

1）有n棵子树的结点中包含n个关键字

2）所有叶子结点包含全部的关键字信息（所有的数据都在叶子结点），指向含这些关键字记录的指针；其中的叶子结点本身依据关键字大小顺序连接

3）所有的分支结点可看出索引，结点中仅含有子树中最大或最小的关键字

2）点的详细解析：

所有的数据都在叶子结点，非叶子结点中存放元素（用于索引）不存放数据，因此每一层可容纳更多的元素，磁盘的IO操作次数相比B树少；

B+树的所有叶子结点使用链表连接，便于区间查找和遍历。

适用于：文件系统的查找、数据库索引