有序表及其应用

当我们学习了各种各样的数据结构之后，就会发现它们最终都只有一个目的：提高数据的查询效率！

当我们以顺序表或者链表组织数据的时候，查询一个数据需要O(n)的时间复杂度。可当数据是海量的时候，O(n)的时间复杂度可吃不消。于是一些牛人就发现：如果将数据有序的组织起来，查找一个数据的时候可以做到O(logn)的时间复杂度。没错，这就是基于有序表的二分查找。

可是，如果数据用链表形式组织起来，查找只能从头到尾。于是基于链式的二分查找的各种数据结构应运而生：二叉搜索树（BST）、平衡二叉树（AVL）、B树、B+树、红黑树、跳表等，这些都可以称为有序表。

红黑树

由于二叉搜索树可能有退化成单链表的可能，所以出现了平衡二叉树（AVL）。每当插入一个数据的时候，通过不断调整树的结构，使得树的左右子树层级不大于1，来保证这颗BST以平衡的姿态使得数据的查询速度接近于二分法查找的速度log(n)，从而避免了BST退化成链表而降低查询效率的可能。

可是正是因为这种完美的平衡反而使得它不完美，因为每次插入操作都可能会引起整颗树通过不断左旋、右旋操作使其达到完美平衡状态，反而降低了效率。

所以红黑树就是一颗不完美的平衡二叉树，通过降低一定的平衡，避免每次操作都带来大量的调整，来提高效率。那么它是怎么实现的呢？

性质

一颗红黑树必须满足：

1. 节点要么黑，要么红。
2. 根结点是黑色的。
3. 每个叶子节点nil是黑色的（个人觉得有没有这个nil叶子节点不影响，只是为了满足性质4而想象出来的）
4. 每个红色节点的两个子节点一定是黑色的。
5. 任意一个节点到每一个节点的路径都包含数量相同的黑节点。

红黑树的自平衡除了左旋和右旋之外，还有一个变色，即红变黑，或黑变红，来满足性质5。所以完美平衡二叉树的平衡依据是平衡因子，而红黑树平衡的依据是性质5，所以也称红黑树为黑色完美平衡。

查找

红黑树的查找操作和AVL树一样，时间复杂度也为O(logn)，主要的区别就是插入操作，多了一步变色。

插入

首先待插入的节点初始时候都是红色。理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

然后查找插入位置插入，再根据不同的情景来自旋，变色来保持平衡。

• 当红黑树为空树，直接插入，节点设为黑色。

• 当插入节点key已经存在，只需要把节点的值更新即可。

• 插入节点的父节点为黑色时候，直接插入。

• 插入节点的父节点为红色时，就需要变色了，因为性质4。

  1. 当叔叔节点存在并且为红节点时

     

     黑红红变为红黑红，之后把pp作为新的插入节点去不断向上调整，如果pp刚好为根节点，那么需要把它重新变为黑色，黑色节点变增加了。这也是唯一一种会增加红黑树黑色节点层数的插入情景。

  2. 叔叔节点不存在或为黑色节点，并且插入节点的父亲节点是祖父节点的左子节点

     插入节点是父节点的左子节点

     

     插入节点是右子节点

     

  3. 叔叔节点不存在或为黑色节点，并且插入节点的父亲节点是祖父节点的右子节点，这种和上面一样，方向变了而已。

删除

删除是红黑树最复杂的操作，过程还是两步：查找目标节点，删除后自平衡。

二叉搜索树的删除一共分三步：

• 若删除结点无子结点，直接删除
• 若删除结点只有一个子结点，用子结点替换删除结点
• 若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点，接着递归删除后继节点。（由于不断用后继节点替换当前节点，对于树来说，真正发生删除的操作总是发生在树末，即前两种情况）

平衡二叉树和红黑树作为特殊的BST也遵循这三步，无非就是删除后需要调整树的结构来达到平衡状态，这里不再深入。

很多编程语言中的有序表底层结构都是红黑树，比如C++中的ordered_map，ordered_set等。

跳表（Skip List）

跳表插入、删除、查找元素的时间复杂度跟红黑树都是一样量级的，时间复杂度都是O(logn)

我们知道单链表的查询操作只能从头到尾，而无法通过二分查找来达到logn级别的查找效率，而跳表就是通过在单链表上加索引使得链表能够实现二分查找。

如果每两个元素建立一个索引节点，（只存储key和几个指针，不需要存储完整的对象）这样的查找过程就和二分查找一样了，时间复杂度为O(logn)。

所以跳表就是通过建立索引来提高查询效率的，典型的“空间换时间”。空间复杂度为O(n)：n/2+n/4+...+2=n-2。

如果每三个节点抽建立一个索引节点，可以减少空间复杂度，但查找效率也会有一定的下降，所以可以根据不同场景来调整这个阈值。

插入

通过查找找到待插入数据在原始链表中的位置的时候，插入即可。但是如果一直往原始链表插入数据而不更新索引的话，极端情况下就会使跳表退化为单链表，所以需要对索引进行维护。

首先需要明白，当数据量足够大的时候，我们在原始链表中随机的选 n/2 个元素做为一级索引是不是也能通过索引提高查找的效率。虽然不是每隔一个元素抽取一个索引节点，但对于查找效率来说，影响不大，尤其是数据量不够大且抽取足够随机的时候。

所以我们维护这样一个索引：随机选 n/2 个元素做为一级索引、随机选 n/4 个元素做为二级索引、随机选 n/8 个元素做为三级索引，依次类推，一直到最顶层索引。

实现过程：

可以在每次新插入元素的时候，尽量让该元素有 1/2 的几率建立一级索引、1/4 的几率建立二级索引、1/8 的几率建立三级索引，以此类推，就能满足我们上面的条件。

当每次有数据插入的时候，先通过概率算法告诉我们这个元素需要插入到几级索引中，然后开始维护索引并把数据插入到原始链表中。

randomLevel() 方法返回 1 表示当前插入的该元素不需要建索引，只需要存储数据到原始链表即可（概率 1/2）

randomLevel() 方法返回 2 表示当前插入的该元素需要建一级索引（概率 1/4）

randomLevel() 方法返回 3 表示当前插入的该元素需要建二级索引（概率 1/8）

randomLevel() 方法返回 4 表示当前插入的该元素需要建三级索引（概率 1/16）

。。。以此类推

既然返回2的时候是建立一级索引，为什么概率是1/4呢？不是应该为1/2嘛？

因为当建立二级索引的时候，同时也会建立一级索引；当建立三级索引时，同时也会建立一级、二级索引。

加入此时需要建立二级索引，那么它的概率为1-1/2-1/4=1/4。

整个维护索引的操作无非是在查找的过程添加一个索引节点而已，每层插入的时间复杂度为O(1)，所以整个插入操作时间复杂度为O(logn)。

删除

删除操作无非是在查找的过程中顺便删掉每层索引的节点，时间复杂度也是O(logn)。

总结

• 跳表是可以实现二分查找的有序链表；
• 每个元素插入时随机生成它的level；
• 最底层包含所有的元素；
• 如果一个元素出现在level(x)，那么它肯定出现在x以下的level中；
• 每个索引节点包含两个指针，一个向下，一个向右

Redis中的有序集合zset底层就是跳表，为什么不使用红黑树呢？

因为zset支持范围查找，按照区间查找数据时，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，非常高效。而红黑树底层是一颗二叉搜索树，它的有序性必须通过中序遍历来实现，效率没那么高。

B树（B-tree）

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个，即每个节点可以拥有更多的子节点，每个节点也可以含有多个关键字。

B-树有如下特点:

1. 所有键值分布在整颗树中（索引值和具体data都在每个节点里）；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；
4. 在关键字全集内做一次查找,性能逼近二分查找；

B-树是专门为外部存储器设计的，如磁盘，它对于读取和写入大块数据有良好的性能，所以一般被用在文件系统及数据库中。

传统用来搜索的平衡二叉树有很多，如 AVL 树，红黑树等。这些树一般应用于加载到内存中的数据的查询。而当数据量非常大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns，而磁盘在 10 ms 左右。速度相差了近 5 个数量级，磁盘读取时间远远超过了数据在内存中比较的时间。所以B树通过降低树的高度，来减少磁盘IO的数量。

查找

多叉的好处很明显，就是为了降低树的高度，因为一次向下查找要读去一次磁盘IO，一般一颗B-树的高度在3层左右。

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

一般根节点是被加载到内存中的，查找时先在节点内部做二分查找，然后定位下一次要查找的节点，进行一次磁盘IO，接该节点读入内存，接着在内存中进行二分查找，直到找到key。

B+树

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

1. 所有关键字存储在叶子节点出现,内部节点(非叶子节点）并不存储真正的 data
2. 为所有叶子结点增加了一个链指针，使得B+树可以顺序访问

因为内节点并不存储 data，所以一般B+树的叶节点和内节点大小不同，而B-树的每个节点大小一般是相同的，为一页。

查找

B+树内节点不存储数据，所以它的查询时间复杂度固定为O(logn)，而B-树不固定，最高位O(1)。

由于B+树叶节点两两相连，所以可以使用范围查询，大大增加区间访问性，B-树不支持范围查询。

B+树比B-树更适合外部存储，因为内节点无data域，每个节点可以索引的范围更大更精确。

磁盘存储的最小数据单元是扇区——512字节

文件系统最小单元是块——4k，一个文件大小为1字节，但也不得不占用磁盘上4KB的空间

InnoDB存储引擎最小存储单元是页——16k（也可以通过参数设置）,假设一行数据1k，一页就可以存储16行这样的数据。

数据库如何通过B+树来组织数据的？

首先所有数据分别存放在不同的页中，除了存放数据的页，还有存放key+指针的索引页，也就是B+树中的内节点，这种页称为索引组织表。

查询过程就是B+树的查找过程，我们通过这棵B+树来查找，首先找到根页，你怎么知道user表的根页在哪呢？

其实每张表的根页位置在表空间文件中是固定的，即page number=3的页

通常一颗B+树可以存放多少行数据呢？

上文我们已经说明单个叶子节点（页）中的记录数=16K/1K=16。（这里假设一行记录的数据大小为1k，实际上现在很多互联网业务数据记录大小通常就是1K左右）。

那么现在我们需要计算出非叶子节点能存放多少指针？

其实这也很好算，我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节

我们一个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。

根据同样的原理我们可以算出一个高度为3的B+树可以存放：1170 * 1170 * 16=21902400条这样的记录。

所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储，一般一张表对应一颗B+树。

在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

Mysql索引为什么使用B+树而不是其他树？

因为B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少

指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低；

字典树

字典树是一种空间换时间的数据结构，又称Trie树，前缀树，典型用于统计、排序、和保存大量字符串。所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

性质

1：根节点不包含字符，除了根节点每个节点都只包含一个字符。root节点不含字符这样做的目的是为了能够包括所有字符串。

2：从根节点到某一个节点，路过字符串起来就是该节点对应的字符串。

3：每个节点的子节点字符不同，也就是找到对应单词、字符是唯一的。

参考链接：
https://www.jianshu.com/p/e136ec79235c

https://www.jianshu.com/p/9d8296562806

https://www.jianshu.com/p/ace3cd6526c4

https://mp.weixin.qq.com/s/NGjJzYGT64uiuwtsR3QKyQ