Redis中支持五种数据类型中有序集合Sorted Set的底层数据结构使用的跳跃表，为何不使用其他的如平衡二叉树、b+树等数据结构呢？
redis的设计目标、性能需求：
redis是高性能的非关系型（NoSQL）内存键值数据库，它以其快速的操作速度而闻名。
读取速度：Redis能实现极高的读取速度，据官方测试报告，可以达到每秒约110,000次读取操作。
写入速度：与读取相比，写入速度略低，但仍然相当可观，官方数据显示，Redis的写入速度大约是每秒81,000次操作。
通过什么数据结构可以实现有序集合？需求：自然有序，查找高速，支持范围查找。
- 传统数组/链表+排序
- 跳跃表（链表的优化–链表+多级索引）
- 平衡二叉树(AVL树、红黑树）
- B+树
1，传统数组/链表+排序
数组或链表可以存储数据，可以新增或修改数据后重新排序，
而在集合排序方面，最快的归并排序也需要O(NlongN)的时间复杂度。
时间不够快，但实现、使用方面简单。
2，跳跃表（链表的优化–链表+多级索引）
跳跃表最早是由William Pugh在1990年提出的，被用来代替平衡树（如AVL树和红黑树）来实现有序集合。跳跃表的查询复杂度为O(log n)，与平衡树相当，但由于其实现较为简单，所以在实际使用中比平衡树更加高效。
例：查找90,增加指针，让指针指向远处个节点，
如上图，共四层，最底层（原链表L1）节点是10 - 20 - 30 -… - 120，中间层L2增加节点10 - 30 - 40 - 60 - 80 - 100 - 120，L2上层L3增加节点10 - 40 - 80 - 120 最高层10 - 120
这样形成三个新的链表，但它包含的节点个数只有原来的一部分；
当我们查找数据之时，先沿着这个最高层链表进行查找。当碰到比待查数据大的节点时，再到中间层，最后回到原来的链表中进行查找。
如查找90，共经历6步。
过程类似二分查找，时间复杂度支持平均O(logN)，最坏O(N)的节点查找，还可以顺序性操作来批量处理节点.
3，平衡二叉树(AVL树、红黑树）
平衡二叉树的查询复杂度为O(logN)，但新增、删除需要调整保持平衡，实现相对复杂；
范围查询方面，平衡二叉树支持范围查询,但是这这种数据结构要范围查找要往回找,即回溯到父结点,而B+树的叶子结点的指针的效率则更高。
4，B+树
B+ Tree是一种经典的多路平衡查找树，它通常被用来实现磁盘上的数据结构。
在B+Tree中，每个节点可以包含多个键值对，而且所有叶子节点都被连接成一个链表。
B+Tree的查询复杂度也是O(logN)，但由于其实现较为复杂，所以在实际使用中通常用于数据库系统等需要高效读写的场景中。
实现方面：跳跃表与平衡二叉树
1，跳跃表
//redis源码中跳跃表结构的实现：
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
sds ele;
double score;//分值
struct zskiplistNode *backward;//后退指针
//层 中每个元素都有一个指向其他节点的前进指针，可以通过这些层来加快访问速度
struct zskiplistLevel {
struct zskiplistNode *forward;//前进指针
unsigned long span;//跨度
} level[];
} zskiplistNode;
实现平衡二叉树、B+树可见原博客
Redis的作者@antirez关于此问题的解答：
1、They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2、A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3、They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
1、它们不是非常内存密集型的。基本上由你决定。改变关于节点具有给定级别数的概率的参数将使其比 btree 占用更少的内存。
2、Zset 经常需要执行 ZRANGE 或 ZREVRANGE 的命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好。
3、它们更易于实现、调试等。例如，由于跳表的简单性，我收到了一个补丁（已经在Redis master中），其中扩展了跳表，在 O(log(N) 中实现了 ZRANK。它只需要对代码进行少量修改。
总结：
- 1，时间复杂度方面：大部分情况下，跳跃表的效率和平衡树媲美；
- 2，算法实现方面：跳跃表的实现比平衡树、b+树更为简单；
- 3，范围查找方面，跳表比平衡树操作要简单，平衡树需要回溯到父结点，条表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历；
- 4，对于小数据集的性能： 在某些场景下，跳表在小数据集上的性能可能优于B+树。跳表的查询操作在某些情况下可能更迅速。