redis为什么采用跳表而不是红黑树？

redis为什么采用跳表而不是红黑树，主要是以下几点原因：
在做范围查找的时候，平衡树比skiplist操作要复杂。
平衡树需要以中序遍历的顺序继续寻找其它不超过大值的节点。
skiplist进行范围查找非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
skiplist需要更少的指针内存。平均每个节点包含1.33个指针，比平衡树更有优势。
从算法实现难度上来比较，skiplist比平衡树要简单得多。

主要基于以下几点：
1、数据结构层面：红黑树的操作（查找、插入及删除）逻辑较复杂，对子树产生一定影响； 而redis的跳跃表skiplist的相关操作简单又快速。
2、算法实现层面： redis的跳跃表 skiplist相比红黑树要简单得多
3、资源使用角度层面： redis的跳跃表 skiplist相比红黑树更有优势

在做范围查找的时候，平衡树比 skiplist 操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在 skiplist 上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而 skiplist 的插入和删除只需要修改相邻节点的指针，操作简单又快速。

从内存占用上来说， skiplist 比平衡树更灵活一些。一般来说，平衡树每个节点包含 2 个指针（分别指向左右子树），而 skiplist 每个节点包含的指针数目平均为 1/(1-p) ，具体取决于参数 p 的大小。如果像 Redis 里的实现一样，取 p=1/4 ，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。

查找单个 key ， skiplist 和平衡树的时间复杂度都为 O(log n) ，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近 O(1) ，性能更高一些。所以我们平常使用的各种 Map 或 dictionary 结构，大都是基于哈希表实现的。

从算法实现难度上来比较， skiplist 比平衡树要简单得多。