Data-Structure

“SkipList, 跳表, 跳跃表” SkipList SkipList(跳表)这种数据结构是由 William Pugh 于1990年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在其中详细描述了他的工作。由论文标题可知，SkipList 的设计初衷是作为替换 平衡树 的一种选择。 我们都知道，AVL树有着严格的O(logN)的查询效率，但是由于插入过程中可能需要多次旋转，导致插入效率较低，因而才有了在工程界更加实用的红黑树。 但是红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，SkipList 需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。 SkipList还有一个优势就是实现简单，SkipList的实现只花了2个小时，而红黑树，我可能得2天。 时隔将近三十多年，SkipList 这种数据结构仍在许多途径有用武之地，比如Redis, 还有Google的著名项目 Bigtable, leveldb 原理及实现 其实跳表就是在普通单向链表的基础上增加了一些索引，而且这些索引是分层的，从而可以快速地查的到数据。 比如我们要查找key为19的结点，那么我们不需要逐个遍历，而是按照如下步骤: 从header出发，从高到低的level进行查找，先索引到9这个结点，发现9 < 19,继续查找(然后在level==2这层)，查找到21这个节点，由于21 > 19, 所以结点不往前走，而是level由2降低到1 然后索引到17这个节点，由于17 < 19, 所以继续往后，索引到21这个结点，发现21>19, 所以level由1降低到0 在结点17上，level==0索引到19,查找完毕。 如果在level==0这层没有查找到，那么说明不存在key为19的节点，查找失败 https://zhuanlan.zhihu.com/p/33674267 skiplist, 红黑树 skiplist 的复杂度和红黑树一样，而且实现起来更简单。 在并发环境下红黑树在插入和删除时需要 rebalance，性能不如跳表。 http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html

“平衡二叉树, 平衡树, AVL树” 平衡树, 平衡二叉树 AVL树 树堆 (Treap) 伸展树 (Splay tree) 红黑树 (Red–black tree) 加权平衡树 (Weight balanced tree) 2-3树 AA树 替罪羊树 AVL树 AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，AVL树是严格的平衡二叉树，平衡条件必须满足 (所有节点的左右子树高度差的绝对值不超过1) 。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况 局限性 由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。 AVL 树是一种平衡二叉树，得名于其发明者的名字 ( Adelson-Velskii 以及 Landis) 。 1: 定义 父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在 编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图 中我们认为树的高度为h=2。 旋转 节点再怎么失衡都逃不过4种情况，下面我们一一来看一下。 ① 左左情况 (左子树的左边节点) 我们看到，在向树中追加“节点1”的时候，根据定义我们知道这样会导致了“节点3"失衡，满足“左左情况“，可以这样想，把这 棵树比作齿轮，我们在“节点5”处把齿轮往下拉一个位置，也就变成了后面这样“平衡”的形式，如果用动画解释就最好理解了。 ② 右右情况 (右子树的右边节点) 同样，”节点5“满足”右右情况“，其实我们也看到，这两种情况是一种镜像，当然操作方式也大同小异，我们在”节点1“的地方 将树往下拉一位，最后也就形成了我们希望的平衡效果。 ③左右情况 (左子树的右边节点) 从图中我们可以看到，当我们插入”节点3“时，“节点5”处失衡，注意，找到”失衡点“是非常重要的，当面对”左右情况“时，我们将 失衡点的左子树进行"右右情况旋转"，然后进行”左左情况旋转“，经过这样两次的旋转就OK了，很有意思，对吧。 ④右左情况(右子树的左边节点) 这种情况和“情景3”也是一种镜像关系，很简单，我们找到了”节点15“是失衡点，然后我们将”节点15“的右子树进行”左左情况旋转“， 然后进行”右右情况旋转“，最终得到了我们满意的平衡。 添加 如果我们理解了上面的这几种旋转，那么添加方法简直是轻而易举，出现了哪一种情况调用哪一种方法而已。 删除 删除方法跟添加方法也类似，当删除一个结点的时候，可能会引起祖先结点的失衡，所以在每次”结点“回退的时候计算结点高度。 https://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html https://blog.csdn.net/u010899985/article/details/80981053 https://cloud.tencent.com/developer/article/1177129

“二叉树” 二叉树 (Binary Tree) 二叉树 (Binary Tree) 是包含n个节点的有限集合，该集合或者为空集 (此时，二叉树称为空树) ，或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。 二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。 @startuml circle 1 circle 2 circle 3 circle 4 circle 5 circle 7 circle 10 circle 11 circle 14 1 -- 2 1 -- 3 2 -- 4 2 -- 5 3 -- 7 5 -- 10 5 -- 11 7 -- 14 @enduml 满二叉树 Full Binary Tree 对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。 ...

“延时队列” https://zhuanlan.zhihu.com/p/266156267 延迟队列 首先，队列这种数据结构相信大家都不陌生，它是一种先进先出的数据结构。普通队列中的元素是有序的，先进入队列中的元素会被优先取出进行消费； 延时队列相比于普通队列最大的区别就体现在其延时的属性上， 普通队列的元素是先进先出，按入队顺序进行处理， 而延时队列中的元素在入队时会指定一个延迟时间，表示其希望能够在经过该指定时间后处理。从某种意义上来讲，延迟队列的结构并不像一个队列，而更像是一种以时间为权重的有序堆结构。 应用场景 我在开发业务需求时遇到的使用场景是这样的，用户可以在小程序中订阅不同的微信或者 QQ 的模板消息，产品同学可以在小程序的管理端新建消息推送计划，当到达指定的时间节点的时候给所有订阅模板消息的用户进行消息推送。 这里不太懂…. 把要发送的模板消息加到延时队列里？ 如果仅仅是服务单一的小程序，那也许起个定时任务，或者甚至人工的定时去执行能够最便捷最快速的去完成这项需求，但我们希望能够抽象出一个消息订阅的模块服务出来给所有业务使用，这时候就需要一种通用的系统的解决方案，这时候便需要使用到延迟队列了。 除了上述我所遇到的这样的典型的需求以外，延迟队列的应用场景其实也非常的广泛，比如说以下的场景: 新建的订单，如果用户在 15 分钟内未支付，则自动取消。 公司的会议预定系统，在会议预定成功后，会在会议开始前半小时通知所有预定该会议的用户。 安全工单超过 24 小时未处理，则自动拉企业微信群提醒相关责任人。 用户下单外卖以后，距离超时时间还有 10 分钟时提醒外卖小哥即将超时。 对于数据量比较少并且时效性要求不那么高的场景，一种比较简单的方式是轮询数据库，比如每秒轮询一下数据库中所有数据，处理所有到期的数据，比如如果我是公司内部的会议预定系统的开发者，我可能就会采用这种方案，因为整个系统的数据量必然不会很大并且会议开始前提前 30 分钟提醒与提前 29 分钟提醒的差别并不大。 但是如果需要处理的数据量比较大实时性要求比较高，比如淘宝每天的所有新建订单 15 分钟内未支付的自动超时，数量级高达百万甚至千万，这时候如果你还敢轮询数据库怕是要被你老板打死，不被老板打死估计也要被运维同学打死。 按时间戳排序，每秒查询15分钟之内创建的订单? 这种场景下，就需要使用到我们今天的主角 —— 延迟队列了。延迟队列为我们提供了一种高效的处理大量需要延迟消费消息的解决方案。那么话不多说，下面我们就来看一下几种常见的延迟队列的解决方案以及他们各自的优缺点。 实现方案 Redis ZSet 我们知道 Redis 有一个有序集合的数据结构 ZSet，ZSet 中每个元素都有一个对应 Score，ZSet 中所有元素是按照其 Score 进行排序的。 那么我们可以通过以下这几个操作使用 Redis 的 ZSet 来实现一个延迟队列: 入队操作: ZADD KEY timestamp task, 我们将需要处理的任务，按其需要延迟处理时间作为 Score 加入到 ZSet 中。Redis 的 ZAdd 的时间复杂度是O(logN)，N是 ZSet 中元素个数，因此我们能相对比较高效的进行入队操作。 起一个进程定时 (比如每隔一秒) 通过 ZRANGEBYSCORE 方法查询 ZSet 中 Score 最小的元素，具体操作为: ZRANGEBYSCORE KEY -inf +inf limit 0 1 WITHSCORES ...

“bloom filter, 布隆过滤器” Data structures are nothing different. They are like the bookshelves of your application where you can organize your data. Different data structures will give you different facility and benefits. To properly use the power and accessibility of the data structures you need to know the trade-offs of using one. 大意是不同的数据结构有不同的适用场景和优缺点，你需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。 在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。如网页 URL 去重、垃圾邮件识别、 大集合中重复元素的判断和缓存穿透等问题。 布隆过滤器 (Bloom Filter) 是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定地误识别率和删除困难。 什么是布隆过滤器 本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构 (probabilistic data structure) ，特点是高效地插入和查询， 可以用来告诉你 “某样东西一定不存在或者可能存在”。 ...

Red-Black Tree, 红黑树, R-B Tree https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md 二叉查找树 由于红黑树本质上就是一棵二叉查找树，所以在了解红黑树之前，咱们先来看下二叉查找树。 二叉查找树 (Binary Search Tree) ，也称有序二叉树 (ordered binary tree) ,排序二叉树 (sorted binary tree) ，是指一棵空树或者具有下列性质的二叉树: 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 任意结点的左、右子树也分别为二叉查找树。 没有键值相等的结点 (no duplicate nodes) 。 因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O (lgn) . (至于n个结点的二叉树高度为lgn的证明，可参考算法导论 第12章 二叉查找树 第12.4节) 。 但二叉树若退化成了一棵具有n个结点的线性链后，则此些操作最坏情况运行时间为O (n) 。后面我们会看到一种基于二叉查找树-红黑树，它通过一些性质使得树相对平衡，使得最终查找、插入、删除的时间复杂度最坏情况下依然为O (lgn) 。 红黑树 前面我们已经说过，红黑树，本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。 但它是如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢？这就引出了红黑树的5条性质: 每个结点要么是红的，要么是黑的。 根结点是黑的。 每个叶结点 (叶结点即指树尾端NIL指针或NULL结点) 是黑的。 如果一个结点是红的，那么它的俩个儿子都是黑的。 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 正是红黑树的这5条性质，使得一棵n个结点是红黑树始终保持了logn的高度，从而也就解释了上面我们所说的"红黑树的查找、插入、删除的时间复杂度最坏为O(log n)“这一结论的原因。 红黑树是不符合AVL树的平衡条件的，即每个节点的左子树和右子树的高度最多差1的二叉查找树。但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高！！！ 这里引用一下知乎上的回答: Answer 1: 如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。 其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。 map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。 作者: Acjx 链接: http://www.zhihu.com/question/20545708/answer/58717264 Answer 2 这个总结比较好: 红黑树的 查询性能略微逊色于AVL树，因为他比avl树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较，但是，红黑树在插入和删除上完爆avl树， avl树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于avl树为了维持平衡的 开销要小得多 ...

B树(B-tree), B+树(B+-tree),B树(B-tree) B树(B-tree), B+树(B+-tree), B*树(B*-tree) B树(B-tree) 一颗m阶的B树定义如下： 1）每个结点最多有m-1个关键字。 2）根结点最少可以只有1个关键字。 3）非根结点至少有Math.ceil(m/2)-1个关键字。 4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。 5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。 注意: 之前有看到有很多文章把B树和B-tree理解成了两种不同类别的树，其实这两个是同一种树; 概念： B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树 (查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构，让我们来看看他有什么特点; 规则： (1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则； (2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外 (注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）； (3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个 (注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2); (4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子; 最后我们用一个图和一个实际的例子来理解B树 (这里为了理解方便我就直接用实际字母的大小来排列C>B>A） B树的查询流程： 如上图我要从上图中找到E字母，查找流程如下 (1）获取根节点的关键字进行比较，当前根节点关键字为M，E<M (26个字母顺序），所以往找到指向左边的子节点 (二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）； (2）拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点； (3）拿到E和F，因为E=E 所以直接返回关键字和指针信息 (如果树结构里面没有包含所要查找的节点则返回null）； B树的插入节点流程 定义一个5阶树 (平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来; 遵循规则： (1）节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1 (这里关键字数>4就要进行节点拆分）； (2）排序规则：满足节点本身比左边节点大，比右边节点小的排序规则; 先插入 3、8、31、11 再插入23、29 再插入50、28 B树节点的删除 规则： (1）节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil (5/2） (这里关键字数<2就要进行节点合并）； (2）满足节点本身比左边节点大，比右边节点小的排序规则; (3）关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放； 特点： B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理 (磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度; 3、B+树 概念 B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别 规则 (1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加； (2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样； (3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。 (4）非叶子节点的子节点数=关键字数 (来源百度百科） (根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1 (来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）; ...

环形队列 环形队列, circle queue 环形缓冲区 (ring buffer）也称作循环缓冲区 (cyclic buffer）、圆形队列 (circular queue）、圆形缓冲区 (circular buffer） 环形队列是在实际编程极为有用的数据结构,它有如下特点。 它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。 因为有简单高效的原因，甚至在硬件都实现了环形队列. 环形队列广泛用于网络数据收发，和不同程序间数据交换 (比如内核与应用程序大量交换数据,从硬件接收大量数据) 均使用了环形队列. 一.环形队列实现原理 内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个的转回是通过取模操作来执行的。 因此环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接，形成一个存放队列的环形空间。 为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。 环形队列的关键是判断队列为空，还是为满。当tail追上head时，队列为满时，当head追上tail时，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断. 如何判断环形队列为空，为满有两种判断方法。 一.是附加一个标志位tag 当head赶上tail，队列空，则令tag=0, 当tail赶上head，队列满，则令tag=1, 二.限制tail赶上head，即队尾结点与队首结点之间至少留有一个元素的空间。 队列空: head==tail 队列满: (tail+1)% MAXN ==head