Redis zset基于跳表实现时查找、插入复杂度是多少?
1 个回答
不必太张扬,是花自然香。ketty查找和插入的时间复杂度都是 O(log n)。跳表是能做二分查找的有序链表,在有序链表上加了多级索引。按标准跳表来看,每一级索引大约是下一级元素个数的一半,高度是 log n,查找时每次大约少一半元素,所以查找是 O(log n)。插入要先找到各层的前置节点,再做链表插入,定位的代价同样是 O(log n),所以插入也是 O(log n)。删除也是这个复杂度,和平衡二叉树接近。
参考来源:https://www.cnblogs.com/cxy2020/p/13799047.html发布于 2026-11-14 19:11 •IP属地 云南举报评论收藏
公众号进入网站体验更佳

