B树  B+树 红黑树详解

常见的查找算法

B树

查找

插入

没有破坏结构

结构破坏

分裂

删除

终端

1 直接删除

2兄弟够借

3兄弟不够借

非终端

1

2

3 

B+树

B+树和B树相比，主要的不同点在以下3项

内部节点中，关键字的个数与其子树的个数相同，不像B树种，子树的个数总比关键字个数多1个

所有指向文件的关键字及其指针都在叶子节点中，不像B树，有的指向文件的关键字是在内部节点中。换句话说，B+树中，内部节点仅仅起到索引的作用，

在搜索过程中，如果查询和内部节点的关键字一致，那么搜索过程不停止，而是继续向下搜索这个分支。

根据B+树的结构，我们可以发现B+树相比于B树，在文件系统，数据库系统当中，更有优势，原因如下：

B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。

B+树的查询效率更加稳定

由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

B+树更有利于对数据库的扫描

B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的range query，B+树有着更高的性能。

从一道索引数据结构面试题看B树、B+树

题目1： Mysql数据库用过吧？l里面的索引是基于什么数据结构。

答：主要是基于Hash表和B+树

题目2： 很好请你说一下B+树的实现细节是什么样的？B-树和B+树有什么区别？联合索引在B+树中如何存储？

答: 首先，数据库使用树型结构来增加查询效率，并保持有序。那么，为什么不使用二叉树来实现数据结构呢，二叉树算法时间复杂度是lg(N)，查询速度和比较次数都是较小的。

实际上，查询索引操作最耗资源的不在内存中，而是磁盘IO。索引是存在磁盘上的，当数据量比较大的时候，索引的大小可能达到几个G。那么，我们利用索引进行查询的时候，不可能把索引直接加载到内存中，只能一次读取一个磁盘页，一个磁盘页对应着一个节点，一次读取操作需要一次磁盘io。

在二叉树查询时，最坏的情况下查找的次数是树的高度，即io次数为树的高度。B-树就是比二叉树“矮胖”的树。

B树的特征如下：

1. 根节点至少有两个子女

2. 每个中间节点包含k-1个元素和k个孩子，其中 m/2 <= k <= m

3. 每个叶子节点包含k-1个元素，其中 m/2 <= k <= m

4. 所有叶子节点位于同一层

5. 节点中的元素从小到大排列，正好是孩子节点的值域。（就是孩子节点的元素都比父节点中元素的最小值大，比父节点元素的最大值小）

B-树查询的次数并不比二叉树的次数小，但是相比起磁盘io速度，内存中比较的耗时就不足为提了。所以只要树的高度足够低，io次数少，就可以提升查找性能。而每个节点中有多个元素，都只在内存中操作。

而B+树是基于B-树的，增加了如下规则：

 

1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

所以，B+树对比B-树有如下好处：

io次数少：B+树中间节点只存索引，不存在实际的数据，所以可以存储更多的数据。索引树更加的矮胖，io次数更少。

性能稳定：B+树数据只存在于叶子节点，查询性能稳定

范围查询简单：b+树不需要中序遍历，遍历链表即可。

红黑树

优缺点

　虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

 

　显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树

磁盘和内存选择B树和红黑树的原因

B+树的高度要比红黑树小，有效减少了磁盘的随机访问
B+树的数据节点相互临近，能够发挥磁盘顺序读取的优势（缓存）
B+树的数据全部存于叶子结点，而其他节点产生的浪费在经济负担上能够接收，红黑树存储浪费小

红黑树常用于存储内存中的有序数据，增删很快，b+树常用于文件系统和数据库索引，因为b树的子节点大于红黑树，红黑树只能有2个子节点，b树子节点大于2，子节点树多这一特点保证了存储相同大小的数据，树的高度更小，数据局部更加紧凑，而硬盘读取有局部加载的优化（把要读取数据和周围的数据一起预先读取），b树相邻数据物理上更加紧凑这一特点符合硬盘进行io优化的特性。b+树在b树基础上进一步将数据只存在叶子节点，非叶子节点不存值只存储值的指向，这使得单个节点能有更多子节点，除此之外将所有叶子节点（值存在叶子节点）放入链表中，使得数据更加紧凑有序，只需要链表（叶子节点）的一次遍历就能获取所有树上的值。b+树这些特性适合用于数据库的索引，mysql底层数据结构就是b+树。

性质

左旋和右旋

public class RedBlackTree {
    private final int R =0;
    private final int B =1;
    private Node root = null;

    class Node{
        int data;
        int color = R;
        Node left;
        Node right;
        Node parent;

        public Node(int data){
            this.data = data;
        }
    }

    public void insert(Node root,int data){//root节点一定不为空。最开始默认进去了

        if(root.data < data){
            //插入到右边
            if(root.right == null){
                root.right = new Node(data);
            }else {
                insert(root.right,data);
            }
        }else {
            if(root.left == null){
                root.left = new Node(data);
            }else {
                insert(root.left,data);
            }
        }
    }
    //左旋
    public void leftRotate(Node node){
        if(node.parent == null){
            Node E = root;
            Node S = E.right;

            //移动S的左子树
            E.right = S.left;
            S.left.parent = E;

            //第二步移动E的指针
            E.parent = S;

            //第三步修改S的指针
            S.parent = null;
        }
    }
}

情况1、2介绍

情况3

情况4

情况5

总结