二叉排序树或平衡二叉树（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+树的所有叶子结点使用链表连接，便于区间查找和遍历。
适用于：文件系统的查找、数据库索引
