3 篇文档带有标签「data structures」

B 树和 B+ 树是磁盘数据库的主力数据结构。B 树在每个节点都存储数据；B+ 树把叶子节点连成链表、把所有数据都下推到叶子层。这一个结构差异决定了所有实际权衡——范围扫描、缓存行为、以及为何几乎所有关系型数据库都使用 B+ 树。

布隆过滤器是一种紧凑的概率集合成员结构——1% 假阳性率约 10 位/元素，零假阴性。本文讲解其工作原理、参数选择的数学、真实系统中的使用（Cassandra、HBase、Chrome、CDN），以及何时应改用计数型 / 布谷鸟 / 商数过滤器等变种。

跳表是一种概率性的多层链表，支持 O(log n) 的搜索、插入与删除。被 LevelDB 的 MemTable、Redis 的 Sorted Set 和 Lucene 的倒排索引采用。本文讲解其工作原理、为何相较于平衡 BST 被选中，以及每个真实实现中的具体权衡。