B+树与二叉树区别是什么？为什么不用红黑树？

红黑树是一个平衡的二叉查找树。有以下几个性质： 1.根节点和叶子节点都是黑色的（这里的叶子节点指的是普通的节点增加的一个黑色的空节点）。 2.红色节点的子节点必须是黑色的，也就是不能有两个红色节点连续。 3.黑色的节点可以连续，但是从根节点到叶子节点的所有路径包含的黑色节点的个数是一致的。(所以根节点到叶子节点的最长路径<=最短路径的两倍) 红黑树是二叉查找树（也就是每个节点的左子树<当前节点的值，右子树所有节点>=当前节点值），但不是严格意义上的平衡二叉树，因为平衡二叉树要求任何节点的左右子树高度差是<=1，红黑树根节点到叶子节点的最长路径会<=最短路径的两倍,所有他是大致意义上的平衡树。 相比于AV树（也就是自平衡的二叉查找树，左右子树高度差不超过1），红黑树插入，删除效率更高。因为不需要保证绝对的平衡，任何不平衡需要的旋转次数不超过3次，即便在最坏的情况下，红黑树能够以O(log(N))的时间复杂度进行搜索、插入、删除操作。 ### 与红黑树的比较 红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，主要有以下两个原因： **（一）更少的查找次数** 平衡树查找操作的时间复杂度和树高 h 相关，O(h)=O(logdN)，其中 d 为每个节点的出度。 红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多，查找的次数也就更多。 **（二）利用磁盘预读特性** 为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。而B+数中存储的叶子节点在内存中是相邻的，这样可以读取会快一些。 **（三）存储更多的索引节点** B+树跟B树的区别就是B+是叶子节点存储数据，非叶子节点(也就是索引节点)只存储索引项，B树是所有节点都存储数据，而每个节点都是磁盘的一个内存页，内存页大小是固定，B+树的每个索引节点可以容纳的索引值更多，与B树相比，B+树的层数更少。