关于Java的二叉树、红黑树、B+树详解

目录

• 1、二叉查找树
• 2、平衡二叉查找树
• 3、红黑树：
• 4、 B树：
• 5、 B+树
• 6、红黑树 VS B+树

数组和链表是常用的数据结构，数组虽然查找快（有序数组可以通过二分法查找），但是插入和删除是比较慢的；而链表，插入和删除很快（只需要改变一些引用值），但是查找就很慢，需要从头开始遍历； 那么有没有一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点呢，那就是接下来要介绍的——树。

1、二叉查找树

特性：

• 1、左子树上所有节点的值均小于它的根节点的值；
• 2、右子树上所有节点的值均大于它的根节点的值；
• 3、左、右子树也分别为二叉排序树。

设计优势

B+树的好处主要体现在查询性能上，由于B+树的中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素，这就意味着，一次性加载到内存中的节点元素更多，从而使得查询时IO次数也更少。(举个简单的例子，一个磁盘页可以加载B树的100个节点元素，但是可以加载B+树的1000个节点元素，那么对于查找999这个数来说，B数需要10次IO，B+数只需要1次IO)

B+树相对B树的优点：

• IO一次读数据是从磁盘上读的，磁盘容量是固定的，取数据量大小是固定的，非叶子节点不存储数据，节点小，磁盘IO次数就少。
• B+树查询性能稳定，因为B+树的查询必须最终查找到叶子节点； 而B树，只要找到匹配元素即可，无论匹配元素处于中间节点，还是叶子节点。所以B树的查询性能并不稳定，最好情况是只查根节点，最坏情况是查到叶子节点
• B+树的所有Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串联起来（可以认为是链表），遍历叶子节点就能获取全部数据，这样就能进行区间访问了。 B树做范围查询，只能繁琐的遍历，但是B+树，只需要查到查找到范围下限以后，遍历叶子节点（有序链表）就可以了。

综合起来，B+树比B树的优势有三个：1、IO次数更少；2、查询性能更佳；3、范围查询简便

场景：Mysql索引

6、红黑树 VS B+树

红黑树的深度比B+树大，当数据量小时，可以把数据完全放到内存中，红黑树的时间复杂度比B树低（不用每次都查到叶子节点），如linux中进程的调度用的是红黑树，Java中HashMap、TreeMap、TreeSet（都在内存中操作）也都是用红黑树实现；

但是，当数据量大时，不能一次性把数据放到内存时，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下；而B树因其读磁盘次数少，具有更快的速度。