数据结构--B树、B+树、红黑树区别

1、B树---多路搜索树（有序）

（1）定义任意非叶子结点最多只有M个儿子；且M>2；

（2）每个非叶子结点存放关键字及其关系（指针） 

         保存键值对（记录表中的主键）、指针（子结点地址）、数据

         比平衡二叉树（AVL）减少了一次IO操作

（3）所有叶子结点位于同一层，且不带信息

          一般b树下会加一层全空的叶子结点，代表查找失败，程序中就是用空指针代表

           查找中也叫做外结点

（4）遵循二叉排序树规则：左<根<右（5）每个节点

优点：

    关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少，

    b树多路有序特点减少了I/O操作

   

2、B 树---多路搜索树（有序）

  （1）B 树是B-树的变体，定义基本和B树相同

  （2）非叶子结点存放关键字的信息，叶子结点存放关键字

  （3）叶子结点在同一层，且用链表连接

   优点：  

       所有数据都按照键值大小顺序放在同一层的叶子节点上，并且所有相邻的叶子节点使用链表进行连接，不再需要中序遍历。

      非叶子节点上只存储key值信息，这样大大加大每个节点存储的key值数量，降低B 树的高度

3、红黑树--平衡二叉排序树（有序）

   （1）根结点是黑的

   （2）基本是一层红的一层黑的，但每层的null结点一定是黑的

            即，除叶子结点外，父子不同色

   （3）平衡二叉排序树

            平衡：|每个结点左孩子高度-右孩子高度|<=1

            二叉排序树：有序

     (4)一棵含有n个节点的红黑树的高度至多为2log(n 1).

         高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个。

   （5）用来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。

  4、应用

        Java集合中的TreeSet和TreeMap，

        C STL中的set、map，

        Linux虚拟内存的管理

参考整理：

https://segmentfault.com/a/1190000020416577

https://segmentfault.com/a/1190000023016648?utm_source=sf-similar-article

https://www.cnblogs.com/skywang12345/p/3245399.html

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