redis为什么使⽤跳表实现有序集合⽽不是红⿊树
⼀、什么是跳表？
  为⼀个值有序的链表建⽴多级索引，⽐如每2个节点提取⼀个节点到上⼀级，我们把抽出来的那⼀级叫做索引或索引层。如下图所⽰，其中down表⽰down指针，指向下⼀级节点。以此类推，对于节点数为n的链表，⼤约可以建⽴log2n-1级索引。像这种为链表建⽴多级索引的数据结构就称为跳表。
⼆、跳表的时间复杂度？
1.计算跳表的⾼度
  如果链表有n个节点，每2个节点抽取抽出⼀个节点作为上⼀级索引的节点，那第1级索引的节点个数⼤约是n/2，第2级索引的节点个数⼤约是n/4，依次类推，第k级索引的节点个数就是n/(2k)**。假设索引有h级别，最⾼级的索引有2个节点，则有**n/(2h)=2，得出
h=log2n-1，包含原始链表这⼀层，整个跳表的⾼度就是log2n。
2.计算跳表的时间复杂度
  假设我们在跳表中查询某个数据的时候，如果每⼀层都遍历m个节点，那在跳表中查询⼀个数据的时间复杂度就是O(m*logn)。那这个m是多少呢？如下图所⽰，假设我们要查的数据是x，在第k级索引中，我们遍历到y节点之后，发现x⼤于y，⼩于后⾯的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每⼀级索引都最多只需要遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是
O(logn)。
三、跳表的空间复杂度及如何优化？
1.计算索引的节点总数redis五种数据结构
  如果链表有n个节点，每2个节点抽取抽出⼀个节点作为上⼀级索引的节点，那每⼀级索引的节点数分别为：n/2，n/4，n/8，
…，8，4，2，等⽐数列求和n-1，所以跳表的空间复杂度为O(n)。
2.如何优化时间复杂度
  如果链表有n个节点，每3或5个节点抽取抽出⼀个节点作为上⼀级索引的节点，那每⼀级索引的节点数分别为（以3为例）：
n/3，n/9，n/27，…，27，9，3，1，等⽐数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取⼀次相⽐，时间复杂度要低不少呢。
四、⾼效的动态插⼊和删除？
  跳表本质上就是链表，所以仅插作，插⼊和删除操时间复杂度就为O(1)，但在实际情况中，要插⼊或
删除某个节点，需要先查到指定位置，⽽这个查操作⽐较费时，但在跳表中这个查操作的时间复杂度是O(logn)，所以，跳表的插⼊和删除操作的是时间复杂度也是
O(logn)。
五、跳表索引动态更新？
  当往跳表中插⼊数据的时候，可以选择同时将这个数据插⼊到部分索引层中，那么如何选择这个索引层呢？可以通过随机函数来决定将这个节点插⼊到哪⼏级索引中，⽐如随机函数⽣成了值K，那就可以把这个节点添加到第1级到第K级索引中。
  Redis中的有序集合是通过跳表来实现的，严格点讲，其实还⽤到了散列表。不过散列表我们后⾯才会讲到，所以我们现在暂且忽略这部分。如果你去查看 Redis的开发⼿册，就会发现，**Redis **的有序集合⽀持的核⼼操作主要有下⾯这⼏个：
插⼊⼀个数据；
删除⼀个数据；
查⼀个数据；
按照区间查数据（⽐如查值在[100, 356]之间的数据）；
迭代输出有序序列。
  其中，插⼊、删除、查以及迭代输出有序序列这⼏个操作，红⿊树也可以完成，时间复杂度跟跳表是⼀样的。但是，按照区间来查数据这个操作，红⿊树的效率没有跳表⾼。
  对于按照区间查数据这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做⾮常⾼效。
  当然，Redis之所以⽤跳表来实现有序集合，还有其他原因，⽐如，跳表更容易代码实现。虽然跳表的实现也不简单，但⽐起红⿊树来说还是好懂、好写多了，⽽简单就意味着可读性好，不容易出错。还有，跳表更加灵活，它可以通过改变索引构建策略，有效平衡执⾏效率和内存消耗。不过，跳表也不能完全替代红⿊树。因为红⿊树⽐跳表的出现要早⼀些，很多编程语⾔中的Map类型都是通过红⿊树来实现的。我们做业务开发的时候，直接拿来⽤就可以了，不⽤费劲⾃⼰去实现⼀个红⿊树，但是跳表并没有⼀个现成的实现，所以在开发中，如果你想使⽤跳表，必须要⾃⼰实现。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。