SkipList

SkipList 跳表

对于二分查找算法,底层依赖的是数组随机访问的特性(连续内存,元素固定大小),因此只能用数组来实现。对于存储在链表中的数据,对链表稍加改造,改造成 SkipList,就可以支持类似”二分”的查找算法。

跳表是一种各方面性能都非常优秀的动态数据结构,可以支持快速的插入、删除、查找操作,写起来也不复杂,甚至可以替代红黑树(Red-black tree)。

Redis 中的 Sorted Set(ZSet) 默认使用 zipList 编码存储数据,实现内存数据压缩,但当数据量超过一定范围时(默认,元素个数超过 128 或者某个元素大小超过 64 字节),为了加快查询效率会换成 skipList 存储数据。

对于单链表来讲,即使其中存储的数据是有序的,想在其中查询数据出来也是需要O(n)的时间去从头开始遍历。要想提高查询效率,可以对链表建立多级索引。

qin

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏

打开支付宝扫一扫,即可进行扫码打赏哦