b树和b+树比较MySQL的innodb搜索引擎使用b+树做索引的优势

为什么选用B 树做索引而不选用二叉树或者B树
b 树 （balance tree） 和 b 树应用在数据库索引， 可以认为是 m 叉的多路平衡查找树， 但是从理论上讲， 二叉 树查找速度和比较次数都是最小的，
为什么不用二叉树呢？ 因为我们要考虑磁盘 I O 的影响， 它相对于内存来说是很慢的。数据库索引是存储在磁盘上的， 当数据量大时， 就不能把整个索引全部加载到内存了， 只能逐一加载每一个磁盘页 （对应索引树的节点） 。 所以我们要减少 I O 次数， 对于树来说， I O 次数就是树的高度， 而 “矮胖” 就是 b 树的特征之一， 它的每个节点最多包含 m 个孩子， m 称为 b 树的阶。 为什么不用B树呢？ b 树， 是 b 树的一种变体， 查询性能更好。 b 树相比于 b 树的查询优势：
1.b 树的中间节点不保存数据， 所以磁盘页能容纳更多节点元素， 更 “矮胖”。 B 树不管叶子节点还是非叶子节 点， 都会保存数据， 这样导致在非叶子节点中能保存的指针数量变少 （ 有些资料也称为扇出） ， 指针少的情况 下要保存大量数据， 只能增加树的高度， 导致 I O 操作变多， 查询性能变低；
2.b 树查询必须查找到叶子节点， b 树只要匹配到即可直接返回。 因此 b 树查找更稳定 （并不慢） ， 必须查 找到叶子节点； 而B树， 如果数据在根节点， 最快， 在叶子节点最慢， 查询效率不稳定。
3.对于范围查找来说， b 树只需遍历叶子节点链表即可， 并且不需要排序操作， 因为叶子节点已经对索引进行 了排序操作。 b 树却需要重复地中序遍历， 找到所有的范围内的节点。
4 hash表不支持模糊查询，范围查询，以及哈希冲突问题

这篇好文章是转载于：学新通技术网