二叉树：
左右两个子节点 可以为空
二叉查找树：
左子树小于根节点，又子树大于根节点
平衡二叉树：
任何节点的左右两个子树的高度相差最大为1,（高度相差大于1会旋转操作）
B-Tree：（平衡多路查找树）
B-Tree是为磁盘等外存储设备设计的一种平衡查找树
系统从磁盘中读取数据是以磁盘块为单位，一次会把统一磁盘的数据都读出来
索引引入的目的是为了快速查询以及更新表中的数据，是有序表，可以用二分查找提高效率
磁盘I/O操作是影响整个B-Tree查找效率的决定因素
若数据量很大则B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率（采用B+Tree的原因）
B+Tree：
B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构
MySQL InnoDB引擎的索引底层实现采用的是B+tree
对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历。
B+Tree相对于B-Tree有几点不同：
- 非叶子节点是叶子节点的索引，。
- 要存储的数据都存放在叶子节点中。
- 叶子节点之间都有一个链指针，不需要遍历整棵树就可以得到所存储的全部数据。
为什么使用B+树？言简意赅，就是因为：
1.文件很大，不可能全部存储在内存中，故要存储到磁盘上
2.索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数（为什么使用B-/+Tree，还跟磁盘存取原理有关。）
3.局部性原理与磁盘预读，预读的长度一般为页数的整数倍
4.数据库利用磁盘预读原理，讲一个节点的大小设置为一页，这样每一个节点只需要一次I/O就可以完全载入
而红黑树的结构，逻辑上很近的节点物理上可能很远，无法利用局部性
B+树比B树更合适作为索引的原因（这里面的两个图）