电子商务作业做网站,网页微信手机登录,网站建设数据库类型,站长网站跳表是有序集合的底层数据结构#xff0c;它其实是链表的一种进化体。正常链表是一个接着一个用指针连起来的#xff0c;但这样查找效率低只有O(n)#xff0c;为了解决这个问题#xff0c;提出了跳表#xff0c;实际上就是增加了高级索引。朴素的跳表指针是单向的并且元素…跳表是有序集合的底层数据结构它其实是链表的一种进化体。正常链表是一个接着一个用指针连起来的但这样查找效率低只有O(n)为了解决这个问题提出了跳表实际上就是增加了高级索引。朴素的跳表指针是单向的并且元素值不能重复redis对其进行了修改回退指针的作用是支持反向遍历。 具体查找过程假设查45那从5的二级索引一下跳到35发现还没找到再跳到55。发现超了那用一级索引试试结果找到了那ok了。需要注意使用高级索引时候底层源码实现时候还有一个对于步长的记录也就是5-35用二级索引记录了步长3
插入的话不会影响当前表中节点的层高因为节点被创建时和层高就已经确定了当然可能会修改插入位置前后结点的关联指针这是链表必然的。 那一个节点层高如何确定 这是在插入时候确定的默认每个节点一开始默认的是1层一级索引都没有每次以25%概率增加1层5.0.5版本最高为64层。不用一个层高数量的比例是因为不想刻意维护这种比例关系导致额外开销。
跳表的平均性能能达到O(logn)并且由于表头有定义查询有序集合元素总数时仅需O(1)
那么为啥redis不用b树呢 因为b树是更多用于磁盘io的其可以降低磁盘io次数。redis是内存中的所以b树这扁平特性没那么重要了并且跳表实现起来简单也不用考虑在中间位置插入后保持平衡的操作。 同样的问题为啥不用红黑树 其实就是因为跳表实现简单占用内存少层高概率25%是可以调的层高越大占用内存越多折中选择并且查询性能和局部性不比红黑树差
