#跳表

什么是跳表

多层的有序链表，越上层，节点数越少

跳表如何查询

从最上面那层开始，从左往右遍历，直到下一个节点比要查询的值大，往下一层走。循环。

跳表的实现结构

为什么用跳表而不用红黑树

跳表的复杂度和红黑树一样都是O(lgn)

但是并发条件下，红黑树插入和删除时，可能需要rebalance整棵树，而跳表更加局部。