红黑树总结

本篇博文主要是对红黑树进行简单的学习，通过本篇博文你将了解到：

红黑树的概念
红黑树算法
mysql为什么使用b+树，而不是红黑树实现

一红黑树的概念

红黑树是一种特殊的二叉搜索树树，也就是在排序树上添加了更多的限制。

1 为何引入红黑树(不平衡问题)

如图是一个基本的3节点二叉搜索树；

search_tree

现在向树中插入7、6、5、4、3五个节点，结果如图

search_tree2

如此就造成了左右子树极大的不平衡。

为了解决这种插入之后的不平衡问题，所以引入了红黑树的概念。

2 红黑树的几点要素

为了解决搜索树插入不平衡问题，红黑树做了一下几个点约定：

首先是有序树；（前提）

节点只有红色、黑色两种颜色
根节点必须是黑色
叶子节点的子节点(BULL)必须是黑色
红色节点的子节点必须是黑色的。
任意节点所有叶子节点路径所包含的黑色节点个数必须一致。

如图：

red_black_tree

3 红黑树节点插入删除调整策略

由于一个红黑树必须包括上述的五点基本要求，所以在新增或者删除一个节点时很可能使得树不成立，所以需要对应的调整策略；

主要有两种调整策略：

变色改变原来节点的颜色进行调整
旋转节点类似于平衡树旋转，RR、RL、LL、LR几种情况，可以看一下高分笔记；

2 红黑树算法

1 红黑树应用举例

首先jdk1.8的hashmap，使用的是数组+链表的实现方式，但是如果链表长度超过8时，会自动调整为红黑树存储。

此外，java treemap实现是基于红黑树

史上最清晰的红黑树讲解（上）

2 红黑树算法实现

未完待续

3 mysql为什么使用b+树，而不是红黑树实现

1 为什么使用b+树，而不是b-树

1 B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。

    所以从Mysql（Inoodb）的角度来看，B+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。 
    那么Mysql如何衡量查询效率呢？– 磁盘IO次数。 B-树/B+树 的特点就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。这是优点之一。 

2 B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。

    这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的，而B树不支持这样的遍历操作。

2 为什么使用b+树，而不是红黑树实现

1 红黑树是二叉树，深度过大，IO读写频繁

  AVL 数和红黑树基本都是存储在内存中才会使用的数据结构。
  在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。
  为什么会出现这样的情况，我们知道要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，B树可以有多个子女，从几十到上千，可以降低树的高度。

2 数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。

为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

3 B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。

    这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的，而B树不支持这样的遍历操作。