B树和红黑树

这两种数据结构经常用作数据库中的索引，其中Mysql底层索引就是用的B+树，而MogonDB用的就是红黑树。本文不会过多的介绍这两个数据结构的操作和特性，主要探讨一下这两种数据结构为什么适合作为数据结构的索引。

B树和B+树

这两种树的数据结构都是从查找二叉树中发展而来，我们都知道查找二叉树的查找效率非常依赖树的高度，如果树过高查找效率就会很低。但是在实际中数据量都是非常多的，所以树也就非常高。所以为了解决这个问题就有了B树。主要是为了降低树高，提高查找效率的。

B树主要是通过一个节点中存多个有序数据降低树高的，然后通过一定的规则来约束树的平衡，就是一直自平衡树。这些规则就是你在网上随便就能搜到的B树的特征。虽然B树已经提搞了搜索效率了，但是对于数据索引这种要求比较高的，还是发展出了B+树。

B+树和B树主要的区别有两个，一个是B+树除了叶子节点以外的节点只存索引，不存具体内容，第二个是B+树叶子节点用指针连接起来构成一个单链表。第一个不同使得B+树有着比B树更小的存储，就减少了磁盘的IO次数增加了查找效率，但是MySQL使用B+树作为索引的数据结构我认为主要是第二个特点。B+树只需要遍历叶子节点就可以遍历整个树，而B树必须使用中序遍历按序扫库。B+树支持范围查询非常方便。

红黑树

红黑树主要是在二叉查找树上发展而来。二叉查找树由于约束严格，非常容易破坏平衡性，所以插入删除的性能要要比红黑树低一点。红黑树是一种非严格的查找二叉树。所以平均性能要优于查找二叉树。