跳跃表

2018年10月9日阅读需 1 分钟

data structures

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

用例

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

参考资料

https://en.wikipedia.org/wiki/Skip_list

保持联系，关注我获取更多内容

Twitter LinkedIn Telegram Discord 小红书

阅读需 1 分钟

布隆过滤器

布隆过滤器是一种数据结构，用于以远高于其他一般算法的空间和时间效率来检索一个元素是否在一个集合中。使用布隆过滤器获得的结果，可能为假阳性匹配，但不可能为假阴性匹配。元素可以添到集合中，但不能删除；添到集合中的元素越多，误报的可能性越大。

data structures

阅读需 3 分钟

一亿美元的遥测错误：OpenAI 的故障教会我们系统设计的知识

OpenAI 最近的故障揭示了现代系统设计的重要见解，突显了保障措施如何无意中成为风险。了解这一亿美元的遥测错误的教训，以及它们如何适用于你自己的技术基础设施。

阅读需 4 分钟

快速介绍 Optimism 架构

什么是 Optimism？它的架构是什么样的？它的构建组件是什么，它们之间如何相互作用？

阅读需 7 分钟

如何设计区块链服务端的架构？

分布式的区块链记账和智能合约系统。要求节点之间不大信任，但是却激励他们互相合作：交易不可逆，不依赖可信的第三方，保护隐私，透露最少信息，一笔钱不能花两次。假设性能不是问题，暂不考虑如何优化性能。

阅读需 9 分钟

设计以人为本的国际化（i18n）工程方案

硅谷公司的产品大多面向全球市场，而国际化正是跨国公司征战全球市场的战略要地。我们这次设计的 i18n 工程方案主要是解决网站和移动 App 开发过程中的三大问题：1. 语言、2. 时间与时区、3. 数字与货币。如同一切软件系统的开发一样，国际化这件事情没有银弹，好的作品都是靠基本功一点一滴磨出来的。

返回所有帖子