跳跃表

983 2018-10-09T19:39:00.000Z

跳跃表本质上是一个允许对其进行二分搜索的链表。它实现这一点的方法是添加额外的节点,使你能够“跳过”链接列表的部分。对于给定一个正反随机数来创建额外的节点,跳跃表具有O(logn)复杂度的查询、插入和删除。

用例

  • LevelDB MemTable
  • Redis 有序集合(Redis SortedSet)
  • 倒排索引(Lucene inverted index)

如果这篇文章对你有帮助

在 Github 上 Follow 我 :)

下载 硅谷io App

关注互联网创业,用移动 App ,随时随地收藏和复习好文章

© 2018 硅谷io
Built with ❤️ in San Francisco