【数据结构】B树和B+树

二叉树

每个节点最多有两个分叉

二叉查找树

在二叉树的基础上增加一个规则，左子树的所有子节点都要小于根节点，右子树的所有子节点都要大于根节点。

平衡二叉树

二叉查找树在数据不均匀时可能会出现斜树的情况。为避免斜树(极端情况下可能是一个链表了)在二叉查找树的规则上增加一个规则，左右两个子树的高度差的绝对值不可以超过1。通过左旋或右旋来平衡树满足以上规则。

AVL树

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
AVL树本质上还是一棵二叉搜索树，它的特点是
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

B树

即多路平衡查找树，满足平衡二叉树的规则的同时它也可以有多个子树，子树的数量取决于根节点中，关键字的数量(根节点描述的是3,5)那么子树的节点数量就是关键字的数量+1既3个(如1,4,6)。通过这一特点在存储同一数据量的情况下，B树的高度是小于平衡二叉树的。

B+树

在B树的基础上增强，B树的数据存储的每一个节点上，而B+树则存储在叶子节点上并且通过链表的方式将叶子节点的所有数据进行连接。B+树的子路数量等于父节点的关键字数量。

为什么用B树或者B+树做索引结构

因为AVL树的高度是高于B树和B+树的。树的高度降低可以减少磁盘的IO增加查找效率