红黑树

1 红黑树特性

1. 每个节点或者是黑色，或者是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。[这里指到叶子节点的路径] 包含n个内部节点的红黑树的高度是O(log(n)).
   

2 红黑树的使用场景

java中使用到红黑树的有TreeSet和JDK1.8的HashMap。
但是问题来了，为什么要使用红黑树，红黑树的插入和删除都要满足以上5个特性，而作非常复杂的操作。
原因：
红黑树是一种平衡树，他复杂的定义和规则都是为了保证树的平衡性。如果树不保证他的平衡性就是下图：很显然这就变成一个链表了。

保证平衡性的最大的目的就是降低树的高度，因为树的查找性能取决于树的高度。所以树的高度越低搜索的效率越高！
这也是为什么存在二叉树、搜索二叉树等，各类树的目的。

B树

概述

B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树（B树是一颗多路平衡查找树）
它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图.

1B树的特性

维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-树算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。”

一棵m阶的B树的满足条件：

每个节点至多有m棵子树
根节点除外，其它每个分支节点至少有【m/2】棵子树
根节点至少有两棵子树（除非B树只包含一个节点）
所有叶子节点在同一层上，B树的叶子节点可以看成一种外部节点，不包含任何信息。
有j个孩子的非叶结点恰好有j-1个关键码，关键码按递增次序排列。
B 树又叫平衡多路查找树。

下图是一个M=4阶的B树

可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素。

B树的插入及平衡化操作和2-3树很相似，这里就不介绍了。下面是往B树中依次插入

6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

动图见此链接
原文链接：https://www.yycoding.xyz/post/2014/3/29/introduce-b-tree-and-b-plus-tree

2、B树的使用场景

B树多用于做文件系统的索引。
那么问题来了：为什么要用B树，红黑树不是就挺好的么？
原因：
B树和二叉树、红黑树相比较，子树更多也就是路数越多，子树月多表示数的高度越低，搜索效率越高，当然如果路数太多就可能变成一个有序数组了（如下图）。所以当然不可能使得路数无限大。

为什么会出现B-树这类数据结构。

传统用来搜索的平衡二叉树有很多，如 AVL 树，红黑树等。这些树在一般情况下查询性能非常好，但当数据非常大的时候它们就无能为力了。原因当数据量非常大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns，而磁盘在 10 ms 左右。速度相差了近 5 个数量级，磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能？减少磁盘 IO 次数，像 AVL 树，红黑树这类平衡二叉树从设计上无法“迎合”磁盘。

一次内存访问、SSD 硬盘访问和SATA 硬盘随机访问的时间分别约是几十纳秒,几十微秒,几十毫秒。

上图是一颗简单的平衡二叉树，平衡二叉树是通过旋转来保持平衡的，而旋转是对整棵树的操作，若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log n（底数为2），这样逻辑上很近的节点实际可能非常远，无法很好的利用磁盘预读（局部性原理），所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。

我们从“迎合”磁盘的角度来看看B-树的设计。

索引的效率依赖与磁盘 IO 的次数，快速索引需要有效的减少磁盘 IO 次数，如何快速索引呢？索引的原理其实是不断的缩小查找范围，就如我们平时用字典查单词一样，先找首字母缩小范围，再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快，B-树每次将范围分割为多个区间，区间越多，定位数据越快越精确。那么如果节点为区间范围，每个节点就较大了。所以新建节点时，直接申请页大小的空间（磁盘存储单位是按 block 分的，一般为 512 Byte。磁盘 IO 一次读取若干个 block，我们称为一页，具体大小和操作系统有关，一般为 4 k，8 k或 16 k），计算机内存分配是按页对齐的，这样就实现了一个节点只需要一次 IO。

上图是一棵简化的B-树，多叉的好处非常明显，有效的降低了B-树的高度，为底数很大的 log n，底数大小与节点的子节点数目有关，一般一棵B-树的高度在 3 层左右。层数低，每个节点区确定的范围更精确，范围缩小的速度越快（比二叉树深层次的搜索肯定快很多）。上面说了一个节点需要进行一次 IO，那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an)，并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。

点评：B树的每个节点，都是存多个值的，不像二叉树那样，一个节点就一个值，B树把每个节点都给了一点的范围区间，区间更多的情况下，搜索也就更快了，比如：有1-100个数，二叉树一次只能分两个范围，0-50和51-100，而B树，分成4个范围 1-25， 25-50，51-75，76-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的

B+树

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比，B+Tree有以下不同点：

每个节点的指针上限为2d而不是2d+1。

内节点不存储data，只存储key；叶子节点不存储指针。

1、B+树的特性

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

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

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

B+树和B树的区别

B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于:

1. 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
2. 为所有叶子结点增加了一个链指针

为什么数据库用B+树不用B树和红黑树

1、首先说红黑树为什么不行：

红黑树必须存在内存里的，数据库表太大了，存不进去。
即使你找到了把红黑树存进硬盘的方法，红黑树查找一个节点最多要查logN层，每一层都是一个内存页（虽然你只是想找一个节点，但硬盘必须一次读一个页。。），那么一共logN次IO，伤不起阿！
所以我们必须考虑减少树的层数来减少IO次数从而加快查询、修改数据库效率，b和b+树都符合这样的性质，它们每个节点的孩子都很多（几十~几千），所以整个树的高度可以压的很低。

比如100000000数据，每个节点有1000个孩子，那么log 1000(100000000)< 3 ，3层就足够存了！

2、先讲下b树和b+树的区别：

b树的所有节点都是数据节点，但b+树只有叶子节点是数据节点，非叶子（内部）节点只起导向作用，不存储实际数据。
b+树的所有数据节点都在最下层（叶子节点层），相邻节点有链表相连。
注意：磁盘读数据读一个字节和读10个字节和读一页时间相差不大的因为磁盘查找时间大多数都花在寻道上，旋转基本不费时

磁盘简化结构图

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

磁盘详细原理可以看这里：MySQL索引背后的数据结构及算法原理

3、再说b树为什么不如b+树：

1 b树的内部节点都是存储实际数据的，比如一个节点是一个页4096字节，其中每条数据128字节，那么一个节点只能存32个数据项，那么对应的孩子节点数最多为33个，这显然不够用。而b+树内部节点只作为导向作用，只存一个整数就可以，4096/4=1024个数据项。这样b+树的每个节点的孩子数更多，整个树的高度就更低，大大增加查询效率。

2 b+树的叶子节点有链表相连，适合范围查询，因为相邻页直接读取就好了。但b树做不到这一点。

B-/B+索引的性能分析