Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

skip-list | TheRiver | Stay Alive #37

Open
RiverFerry opened this issue Nov 9, 2020 · 0 comments
Open

skip-list | TheRiver | Stay Alive #37

RiverFerry opened this issue Nov 9, 2020 · 0 comments
Labels
c080d30eb6a77262f70f8fb41f6567b2 Gitalk

Comments

@RiverFerry
Copy link
Owner

https://riverferry.site/2020-11-06-skip-list%20in%20redis/

在计算机科学中，跳跃列表是一种数据结构。它使得包含n个元素的有序序列的查找和插入操作的平均时间复杂度都是O(log n)，优于数组的O(n)复杂度。快速的查询效果是通过维护一个多层次的链表实现的，且与前一层（下面一层）链表元素的数量相比，每一层链表中的元素的数量更少（见右下角示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c080d30eb6a77262f70f8fb41f6567b2 Gitalk
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@RiverFerry