主题对照

存储常用数据结构

比较布隆过滤器、跳表、LSM 树、Merkle 树、Cuckoo 哈希等在存储系统中以空间或精度换效率的数据结构。

108 张卡片 · 30 本书

本层 108 张卡片 · 含下级覆盖 108 张卡片

本主题的卡片

大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构

布隆过滤器

布隆过滤器用多个哈希函数和位数组判断成员是否可能存在。它允许误判存在但不误判不存在,适合在磁盘访问前快速过滤无效查询,用少量内存换掉大量随机 I/O。

查看卡片与原书出处

大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构

SkipList随机索引

SkipList 用随机层级给有序链表增加远跳指针,平均查找、插入、删除复杂度接近 O(logN)。它不需要复杂旋转,适合内存有序表,Redis Sorted Set 和 LevelDB MemTable 都受益于这种简洁性。

查看卡片与原书出处

大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构

LSM写读取舍

LSM 树把随机写先落到内存和顺序日志,再批量合并成磁盘有序文件。它用读路径变长、后台合并和写放大,换取高吞吐写入;Bloom Filter 和缓存常用于弥补读损失。

查看卡片与原书出处

大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构

Merkle定位差异

Merkle 树把数据块哈希逐层汇总成根哈希。两个副本只需比较树节点,就能快速定位少量不同的数据范围,适合副本修复、反熵同步和内容完整性校验。

查看卡片与原书出处

大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构

压缩换传输

压缩的核心不是永远追求最高压缩率,而是在 CPU、磁盘、网络之间重新定价。Snappy 选择较快压缩解压速度,适合 MapReduce 中间结果这类受吞吐和流水线延迟约束的场景。

查看卡片与原书出处

大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构

Cuckoo驱逐冲突

Cuckoo Hashing 为元素准备多个候选位置,冲突时把旧元素“踢出”并递归安置。它让查询保持常数时间,但插入可能触发连锁迁移,空间利用率和重建策略决定稳定性。

查看卡片与原书出处

数据密集型应用系统设计 · 存储与检索

索引以写入换读取

最简单的数据库把键值对追加到文件末尾,读取时从头扫描找键最后一次出现的位置。追加写很快,读取却是 O(n),数据一多就不可用。索引是从主数据派生的附加结构,像路标一样加快查找,但每次写入都要同步维护它,所以写入很难快过纯追加。这是存储系统的根本权衡:好的索引显著加快读,每多一个索引就拖慢写。因此数据库不会默认给所有内容建索引,而要由开发者按应用的查询模式挑选收益最大、开销最小的索引。

查看卡片与原书出处

数据密集型应用系统设计 · 存储与检索

哈希索引与段压缩

[[索引以写入换读取]]最简单的实现方式是哈希索引:维护一个 内存中的哈希映射,把每个键映射到数据文件里对应值的字节偏移量,写入时同步更新这个 映射,读取时先查哈希映射拿到偏移量,再对文件做一次seek读取——Bitcask(Riak默认 存储引擎)就是这样做的。为了避免仅追加写入耗尽磁盘空间,日志被拆成固定大小的段, 写满一个段就开新段,旧段可以在后台做压缩(丢弃同一个键的旧版本,只留最新值),并且 可以顺便把多个段合并成更大的段——因为段一旦写入就不再修改,合并只需要写一个新文件, 合并期间旧段仍可正常提供读写服务,合并完成后再把读请求切到新段、删除旧段。这种设计 天然要求单个写入线程(写入严格按顺序追加)配合多线程读取(不可变段可以被安全并发 读取)。哈希索引最大的两个局限是:哈希映射必须完全放进内存,键的数量一旛超出可用 内存就无法工作(磁盘上的哈希映射需要大量随机I/O,扩容和哈希冲突处理都很昂贵); 以及范围查询效率低下——想查”kitty00000到kitty99999之间的所有键”,只能在哈希映射 里逐个单独查找,完全无法利用”相邻键”这个概念,因为哈希函数本身就是打乱顺序的。

结构图:

flowchart TD
    A[写入] --> B[追加到当前日志段文件]
    B --> C[同步更新内存哈希映射: 键→字节偏移量]
    C --> D[段写满后开启新段]
    D --> E[旧段后台压缩: 丢弃重复键, 只留最新值]
    E --> F[多个段合并为更大新段]
    A -.单写入线程, 保证顺序追加.-> A
    F -.段不可变, 可安全被多线程并发读取.-> F
    G[哈希映射必须完全放入内存] -.键量超出内存即失效.-> G
    H[无法高效范围查询] -.哈希打乱了键的顺序.-> H
查看卡片与原书出处

数据密集型应用系统设计 · 存储与检索

SSTable的排序收益

针对[[哈希索引与段压缩]]的局限,只需让段文件中的键值对按键排序、每个键在合并后的段中只出现一次,这就是 SSTable。好处有二:合并段像归并排序,并排读取各段,相同键保留较新段的值,文件大于内存也不必把键全载入内存;内存索引可以稀疏,知道 handbag 与 handsome 的偏移量,就能推断 handiwork 在二者之间,跳到前者后扫描即可。一次排序同时解决了合并效率和索引内存两个问题。

查看卡片与原书出处

数据密集型应用系统设计 · 存储与检索

LSM树与预写日志

要让传入写入首先满足[[SSTable的排序收益]]要求的”按键排序”, 最实际的办法是先在内存里维护一棵平衡树(如红黑树,称为内存表memtable)——插入 可以任意顺序,读取时天然按排序顺序输出。完整流程是:写入先加入内存表;内存表长大 超过阈值(通常几兆字节)后,把它整体高效地写成一个新的SSTable文件(因为树里的数据 已经是排序好的),随后新的写入切换到一个新的内存表实例;读取时依次查内存表、最近的 磁盘段、再下一个较旧的段;后台不断运行合并和压缩流程,组合段文件、丢弃被覆盖或 删除的值。这个方案唯一的弱点是:如果数据库崩溃,内存表里尚未落盘的最近写入会丢失。 解法是额外维护一份磁盘上的预写式日志(WAL):每次写入立即被追加到这份日志(不要求 排序,它唯一的用途是崩溃后重建内存表),一旦对应的内存表已经成功写成SSTable,这份 日志就可以被丢弃。这套算法正是LevelDB、RocksDB以及受Google Bigtable启发的Cassandra、 HBase等存储引擎(统称LSM树,日志结构合并树)的核心思路:即使数据集远大于可用内存 依然能正常工作,因为数据按排序存储所以范围查询高效,又因为磁盘写入始终是连续的 所以能支持很高的写入吞吐量。

结构图:

flowchart TD
    A[写入请求] --> B[追加到WAL: 未排序, 仅用于崩溃恢复]
    A --> C[写入内存表memtable: 排序的平衡树]
    C -->|超过阈值大小| D[整体写成新SSTable文件]
    D --> E[切换到新内存表实例]
    D -->|落盘成功| F[对应WAL可丢弃]
    G[读取请求] --> H[先查内存表]
    H --> I[再查最近的磁盘SSTable段]
    I --> J[依次查更老的段]
    K[后台合并压缩流程] -.持续组合段文件, 丢弃覆盖/删除的值.-> I
查看卡片与原书出处

数据密集型应用系统设计 · 存储与检索

布隆过滤器省磁盘读

[[LSM树与预写日志]]有个性能陷阱:查找不存在的键最慢,要查完内存表和每一个磁盘段才能下结论。布隆过滤器是内存高效的近似集合结构,能快速回答“某键是否可能存在”。它可能误报存在,但绝不误报不存在:若它说不存在,就一定不存在,可以直接跳过该段的磁盘读取;说可能存在时再去查,偶尔白查一次也不影响正确性。这是用轻微、可控的误判率换取大量无谓磁盘 I/O 的经典权衡。

查看卡片与原书出处

数据密集型应用系统设计 · 存储与检索

B树与页面结构

和SSTable/LSM树按可变大小段追加写入的思路完全不同,B树把数据库分解成固定大小的 页面(传统上4KB,贴合底层磁盘的固定块结构),每次只读写一个页面。每个页面有自己的 地址,可以像指针一样被其他页面引用,从而构成一棵页面树:从根页面开始查找,每个 非叶页面包含若干键和对子页面的引用,每个子页面负责一段连续的键范围;一路往下直到 叶页面,叶页面包含每个键的内联值或指向值所在位置的引用。一个页面里子页面引用的 数量叫分支因子,实践中通常是几百,这保证了含n个键的B树深度是O(log n)——分支因子 500的4KB页面构成的四层树能存储多达256TB,绝大多数数据库都能塞进三四层B树,查找 不需要追踪很多层页面引用。更新一个已有键:找到含该键的叶页面,改值,把整页写回 磁盘(对该页的所有引用保持有效);插入一个不属于任何现有页面空间的新键:如果目标 页没有足够空间,就把它拆成两个半满页面,并更新父页面反映新的键范围划分——这意味着 一次插入可能需要连续覆盖好几个不同页面,如果数据库在只写完部分页面时崩溃,就会 留下损坏的索引(比如出现一个不属于任何父页面的孤儿页面)。为此B树实现通常配一份 额外的预写式日志(WAL,也叫重做日志):每次B树修改先记进这个仅追加文件,数据库 崩溃后重启时用WAL把B树恢复到一致状态。

结构图:

flowchart TD
    A[根页面] -->|按键范围引用子页面| B[中间页面]
    B -->|继续细分键范围| C[叶页面: 含键的内联值或引用]
    D[更新已有键] --> D1[找到叶页面, 改值, 整页写回磁盘]
    E[插入导致页面空间不足] --> E1[拆分为两个半满页面]
    E1 --> E2[更新父页面反映新的键范围划分]
    E2 -.多页面连续覆盖, 崩溃时可能损坏.-> F[预写式日志WAL先记录每次修改]
    F -.崩溃重启后用WAL恢复B树到一致状态.-> F
查看卡片与原书出处

数据密集型应用系统设计 · 存储与检索

B树与LSM树的权衡

[[LSM树与预写日志]]和[[B树与页面结构]]的经验法则是:LSM树写入更快,B树读取更快,但这只是起点,真正 的权衡藏在细节里。写放大是理解两者代价的关键概念——”数据库生命周期中每次写入用户 数据,最终导致对磁盘执行多次实际写入”。B树至少要写两次每一份数据:一次写WAL,一次 写树页面本身(即使页面里只有几个字节变了,也要整页重写,某些引擎甚至覆盖同一页面 两次以防电源故障导致页面部分更新)。LSM树因为反复压缩合并SSTable,同样会重写数据, 但通常写放大更低、且是把随机写转成顺序写紧凑的SSTable文件(不必覆盖树中多个分散 页面),因此往往能支持比B树更高的写入吞吐量,在磁盘旋转的机械硬盘上这个差异尤其 明显;LSM树也因为不是面向页面、且定期重写去除碎片,磁盘占用通常比B树更紧凑(B树 的页面分裂会留下未充分利用的空间)。代价方面:LSM树的压缩过程会和正在进行的读写 竞争有限的磁盘带宽,如果压缩跟不上写入速率,未合并段会越堆越多、读取要检查更多 段而变慢,直到磁盘空间耗尽——而且多数基于SSTable的引擎不会主动限制写入速率,需要 人工监控;这导致LSM树查询响应时间在高百分位点上有时会明显不可预测,不如B树的行为 稳定。此外B树有个结构性优势:每个键只存在于索引里的一处位置,而日志结构引擎可能 在不同段里保留同一个键的多个副本,这让B树更适合需要基于键范围加锁来实现强事务 隔离的数据库——锁可以直接挂在B树上,这一点将在事务章节详述。

结构图:

flowchart LR
    A[LSM树] --> A1[写放大通常更低, 顺序写紧凑SSTable]
    A --> A2[写吞吐量通常更高]
    A --> A3[压缩与读写竞争磁盘带宽, 高百分位延迟不可预测]
    A --> A4[同一键可能有多副本分散多段]
    B[B树] --> B1[每份数据至少写两次: WAL+页面本身]
    B --> B2[读取性能更可预测]
    B --> B3[每个键只存在索引一处位置]
    B3 --> B4[更适合基于键范围加锁的事务隔离]
查看卡片与原书出处

数据密集型应用系统设计 · 存储与检索

堆文件聚簇与覆盖索引

索引中的值可以是数据本身,也可以是指向数据的引用,分三个层级。堆文件:索引只存指针,数据存在无序的堆文件中,多个二级索引不重复存数据,更新不变大时可原地覆盖,但每次查询多一次跳转。聚簇索引:行数据直接存进索引,省去跳转,如 InnoDB 的主键,二级索引引用主键。覆盖索引:把部分列存进索引,让某些查询只靠索引就能返回。数据离索引越近读得越快,代价是占用更多空间、写入要维护更多副本并保证它们事务一致。

查看卡片与原书出处

数据密集型应用系统设计 · 存储与检索

多列查询与多维索引

查询多列时常用连接索引,把多个字段拼成一个键,如电话簿的“姓 + 名”。它能按姓或按姓名组合查,却不能单按名查,因为名在排序中处于次要位置。面对地理范围这类真正的多维查询它彻底失效:按纬度范围查得的结果里,经度几乎任意分布。解法是专门的多维索引,如用空间填充曲线把二维位置转成一个数,或用 R 树等空间索引。这不限于地理数据,按 RGB 找颜色范围的商品、按日期与温度查观测记录也都适用。

查看卡片与原书出处

数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引

表空间的逻辑存储结构

关系数据库的逻辑模型允许一张表无限增长,但操作系统的文件系统对 单个文件的大小有硬性上限(如FAT32限制单文件4GB),这个矛盾如果 用”一张表对应一个文件”的朴素方案解决,表一旦超出文件系统上限就 无法继续增长。段页式存储结构(如Oracle采用的方案)用多层逻辑单位 把这个矛盾拆解开:表空间是最外层的逻辑容器,其下由若干段组成 (数据段/索引段/临时段/回滚段,分别对应数据本身/索引/排序连接等 中间结果/事务回滚信息四类不同用途),每个段又由若干区组成,每个 区由若干连续的数据块组成——数据块是逻辑上最小的存取单元,与操作系统 的磁盘文件块按整数倍对应。表空间在物理层面对应一到多个数据文件, 一个表空间可以横跨多个物理文件,这正是突破单文件大小限制的关键: 当表空间需要继续增长、当前数据文件已达上限时,只需要给这个表空间 再挂一个新的数据文件,逻辑上表空间依然是一个连续的整体,物理上却 可以分散在任意多个文件甚至任意多块磁盘上。这套多层映射的本质是 在逻辑连续性和物理文件的硬限制之间插入一层可以自由扩展的中间层, 让上层的关系数据操作完全不需要感知底层文件系统的容量约束。

结构图:

flowchart TD
    A[表空间 Tablespace<br/>逻辑上可对应多个物理文件] --> B[段 Segment<br/>数据段/索引段/临时段/回滚段]
    B --> C[区 Extent<br/>连续的数据块集合]
    C --> D[数据块 Block<br/>逻辑最小存取单元]
    D -.按整数倍对应.-> E[磁盘文件块<br/>操作系统最小存取单元]
    A -.物理映射.-> F[数据文件1]
    A -.物理映射.-> G[数据文件2...N<br/>可分散在不同磁盘]
查看卡片与原书出处

数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引

三种表组织方式

表在磁盘上有三种组织方式,在写入代价与顺序读取代价之间取舍。堆存储不关心顺序,写入最便宜,但物理顺序与逻辑顺序无关,范围查询只能全表扫描或借助索引。顺序存储让记录按某属性值物理排列,范围查询可以顺序读取,但插入可能要挪动后续所有记录或维护复杂的指针链,成本随数据量急剧上升。索引存储是折中:数据按 B 树、哈希等索引结构组织,既能快速定位又不必物理挪动数据,因此成为多数数据库的默认方式。

查看卡片与原书出处

数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引

存储引擎的四模块

存储引擎不是一个笼统的黑盒,而是拆成四个职责边界清晰的模块协同 工作。文件管理模块封装操作系统的文件功能,把数据字典、数据文件、 索引文件、回滚文件、日志文件等组织成表空间对应的文件组,并把逻辑 数据块与物理磁盘文件块对应起来——它是所有上层模块与操作系统之间 的唯一接口。缓冲区管理模块负责把近期或频繁使用的数据块缓存在内存 里,让上层模块发出读写命令时不需要关心数据到底在内存还是磁盘上, 直接从缓冲区读写即可,从而减少磁盘I/O——这是存储引擎能兼顾正确性 与效率的关键中间层。数据字典管理模块专门管理数据库的元数据(表结构、 索引定义等),因为元数据被频繁访问,通常也放在共享内存缓冲区里, 它的增删改操作跟一般数据表的增删改操作走的是同一套机制。存取控制 管理模块是面向上层(查询执行引擎等)的统一接口,提供创建/删除关系、 修改结构、管理约束、增删改查记录等逻辑操作,内部再调用前三个模块 完成具体工作。正是因为存取控制管理模块对上层的接口是固定的,MySQL 才能把这个接口独立出来,让不同的存储引擎(InnoDB、MyISAM等)各自 实现底层细节,对上层应用保持一致的使用体验——这是MySQL插件式存储 引擎架构的基础。

结构图:

flowchart TD
    A[查询执行引擎等上层模块] --> B[存取控制管理模块<br/>统一对外接口]
    B --> C[文件管理模块<br/>封装操作系统文件功能]
    B --> D[缓冲区管理模块<br/>内存缓存减少磁盘I-O]
    B --> E[数据字典管理模块<br/>管理表结构等元数据]
    C --> F[磁盘: 数据文件/索引文件/日志文件]
    D -.数据不在内存时.-> C
查看卡片与原书出处

数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引

聚簇索引与索引类型

索引顺序与数据物理存储顺序一致的是聚簇索引,否则是非聚簇索引。数据只能有一种物理顺序,所以每张表最多一个聚簇索引。聚簇索引利于范围查询和连接:相关记录物理相邻;还可为常一起连接的两张表按同一关键字聚簇,使相关数据落在同一块。代价是增删要物理移动数据,多表聚簇还可能破坏其他索引,须谨慎。另一条独立的分类线是主码索引、唯一性索引和普通索引:主码索引一定唯一,唯一性索引不一定是主码索引。

查看卡片与原书出处

数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引

B树索引结构与效率

B树(阶为M)用”变宽降高”的思路提升查询效率:每个非叶子节点最多可以 容纳M−1个关键字、对应M个子节点指针,节点关键字按顺序排列,每个 指针指向的子树里所有关键字都落在该指针左右两个相邻关键字之间—— 这个排列规则让查询过程变成”在当前节点内二分查找定位到该往哪个指针 走,再进入下一层重复此过程”,而不需要像二叉树那样逐层只能对比一次。 “多路”(每节点能放多个关键字、指向多个子节点)换来的直接好处是树的 高度大幅降低——阶M越大,同样数据量下树的层数越少,磁盘I/O次数 (通常与树高成正比)也越少,这正是B树被设计成”胖而矮”而非”瘦而高”的 原因:磁盘I/O的成本远高于内存内比较的成本,用节点内的多次内存比较 换取更少的磁盘访问次数是划算的交易。”平衡”要求所有叶子节点必须位于 同一层,插入或删除关键字导致某条路径变短变长时,必须做节点分裂/合并 等调整操作以恢复平衡——这保证了从根到任意叶子的查询路径长度始终 一致,不会出现某些查询快、某些查询慢的不确定性。B树索引可以和数据 存储在同一文件(此时叶子节点直接存数据)或分开存储(叶子节点存指向 数据的指针),查询的时间复杂度约为O(log_M N),其中M越大意味着树越 矮,实践中M的选择要综合考虑磁盘块大小和单条记录大小。

结构图:

flowchart TD
    A["根节点: 1~M-1个关键字<br/>1~M个子节点指针"] --> B["非叶子节点: ⌈M/2⌉-1~M-1个关键字"]
    A --> C["非叶子节点: ⌈M/2⌉-1~M-1个关键字"]
    B --> D[叶子节点<br/>所有叶子位于同一层]
    B --> E[叶子节点]
    C --> F[叶子节点]
    C --> G[叶子节点]
查看卡片与原书出处

数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引

B+树的叶子链表

B+ 树是[[B树索引结构与效率]]的变种,改动在于数据存在哪一层:B 树每个关键字都关联数据指针,B+ 树把数据关联全部下沉到叶子节点,非叶子节点的关键字只作为子树最小关键字的路标。好处有二:非叶子节点不存数据指针,能容纳更多关键字,树更矮;叶子节点从左到右用指针串成有序链表。所以范围查询和按序扫描全表在 B+ 树上明显更快:B 树要在树中反复定位,B+ 树只需一次定位加一次线性遍历。

查看卡片与原书出处

数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引

哈希索引的冲突消解

哈希索引把关键字通过哈希函数直接映射成存储地址,插入删除修改的 理想时间复杂度是O(1),但代价是完全丢失顺序信息(只支持等值查询, 范围查询、排序扫描效率和无序表相同)。真正决定哈希索引好不好用的, 是冲突(不同关键字映射到同一地址)发生后怎么处理,处理思路分两大类。 内消解法在哈希表本身的存储区域内解决冲突:线性探查法从冲突位置起 逐个往后找空位插入;双哈希探查法用第二个哈希函数决定探查步长, 让冲突后的查找路径分散得更均匀,减少”扎堆”现象——但内消解法的共同 局限是存储区域大小固定,随着数据填满存储区,冲突只会越来越频繁, 无法从根本上缓解。外消解法在哈希表存储区之外解决冲突:溢出区法给 冲突的数据另开一块空间顺序存放,溢出量小时效率尚可,溢出量大时性能 急剧下降;链地址法把哈希值相同的数据组织成链表挂在对应位置,应用 最广泛,因为链表可以无限延伸、不受固定存储区大小限制。衡量哈希表 “满”的程度用负载因子(已存储数据项数/存储区可容纳数据项数)表示: 负载因子太小意味着空间浪费,太大意味着冲突频发、增删改查效率骤降, 内消解法通常要求负载因子不超过0.7,而外消解法里负载因子本质等价于 链表平均长度,理论上可以容忍更大的负载因子,但链表过长时查询时间会 退化成链表长度的线性函数。

结构图:

flowchart TD
    A[哈希冲突消解] --> B[内消解法<br/>在固定存储区内解决]
    A --> C[外消解法<br/>用额外空间解决]
    B --> B1[线性探查法: 逐个往后找空位]
    B --> B2[双哈希探查法: 第二哈希函数决定步长]
    C --> C1[溢出区法: 冲突数据存入独立溢出区]
    C --> C2[链地址法: 相同哈希值组成链表]
    B1 -.负载因子建议不超过0.7.-> D[数据填满后冲突必然加剧]
    C2 -.负载因子约等于链表平均长度.-> E[理论上可容忍更大负载因子]
查看卡片与原书出处

数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引

位图R树与倒排索引

除了通用的B树和哈希索引,还有三种为特定数据形态量身定制的索引结构, 各自解决的是B树/哈希索引不擅长的问题。位图索引用一串二进制位表示 “哪些记录取某个特定值”(每个可能取值对应一个位图,第i位为1表示第i条 记录取这个值),代价是空间极小(百万条记录的一个位图仅占约122KB) 且增删改查都能用位运算完成、速度很快,但它只适合取值种类少、重复率 高的字段(如性别、地区)——取值种类一多,位图数量跟着暴增,查询 效率反而下降;同时因为每次数据修改都要更新对应位图,它不适合频繁 写入的场景。R树是B树在高维/空间数据上的扩展,用最小外接矩形(MBR) 逐层框定空间范围,节点越往上框住的空间越大——本质上和B树一样是 “先粗筛大范围、再逐层精确定位”,只是把B树里”关键字区间”的概念换成 了”空间矩形区域”,主要用于地理信息系统这类需要按空间位置查询的场景, 增删改查操作的思路与B树完全类似。倒排索引和一般索引的存储方向正好 相反:一般索引存”关键字→数据位置指针”,倒排索引存”数据值→包含该值 的文档/记录位置列表”,天然适合全文检索场景(如Lucene的实现)—— 给定一个查询词,直接查倒排表就能拿到所有包含这个词的文档,不需要 像一般索引那样先确定要查哪个字段再定位关键字。三者的选型逻辑是: 取值集中且读多写少选位图索引,空间/多维数据选R树索引,全文检索选 倒排索引。

结构图:

flowchart TD
    A[特殊场景索引选型] --> B{数据特征}
    B -->|取值种类少+重复率高+读多写少| C[位图索引<br/>每位代表一条记录,位运算高效]
    B -->|空间/多维数据| D[R树索引<br/>B树的空间扩展,用最小外接矩形逐层框定]
    B -->|全文检索场景| E[倒排索引<br/>存'数据值→文档位置列表'而非'关键字→数据指针']
查看卡片与原书出处

深入浅出SSD:固态存储核心技术、原理与实战 · SSD核心技术:FTL

映射表是索引

L2P 映射表就是 SSD 内部的索引:主机拿 LBA 访问,控制器用映射表找到物理页。它越常驻快速内存,随机读越少一次闪存访问;DRAM-less 设计便宜省电,却常付出随机读性能。

查看卡片与原书出处

软件架构设计_大型网站技术架构与业务架构融合之道 · 数据库

B+树容量依赖假设

原书用高扇出解释B+树为什么通常很矮:若内部页可容1000个分支,叶页可容200条记录,三层模型约能表示2亿条记录。但16KiB叶页放200条100字节记录已超页容量,书中数量假设不自洽。若只按100万叶页估算则约15.3GiB;记录大小、页填充率及索引开销改变实际容量,不能当作容量保证。

查看卡片与原书出处

软件架构设计_大型网站技术架构与业务架构融合之道 · 高并发问题

LSM树替代随机写

LSM把更新先写入内存有序结构与WAL,再将数据成批刷新、合并为有序磁盘文件,减少逐次随机写。代价包括合并开销和读多个层次。业务若借鉴“内存更新加日志”,还须保证更新与日志的一致性及恢复协议,不能把Redis扣减与另写日志两次调用自动视为原子动作。

查看卡片与原书出处

App后台开发运维和架构实践 · MongoDB——App后台新兴的数据库

位置查询用空间索引

LBS 查询看似是“找附近的人”,实质是空间距离检索。用地理位置索引或 geohash 预编码,把二维坐标转成可索引的数据结构,才能避免在海量坐标上逐条计算距离。

查看卡片与原书出处

App后台开发运维和架构实践 · App后台架构剖析

地理邻域要补边

geohash 前缀能把坐标映射到网格,但目标点靠近网格边界时,最近对象可能落在相邻格子。附近查询不能只查当前格,还要补查周围区域,再用真实距离过滤。

查看卡片与原书出处

Ceph之RADOS设计原理与实现 · 高效本地对象存储引擎——BlueStore

BlueStore直管设备

BlueStore绕过本地文件系统,直接管理裸块设备,以减少FileStore时代文件系统语义、日志和对象语义之间的重复开销。它把对象存储引擎变成更贴近介质的实现。发散:越底层的抽象越能榨出性能,但也要自己承担空间、元数据和恢复复杂度。

查看卡片与原书出处

Ceph之RADOS设计原理与实现 · 高效本地对象存储引擎——BlueStore

RocksDB管元数据

BlueStore把对象元数据、空间信息等结构化状态放入RocksDB,用键值数据库承担有序查询和持久化更新。对象数据走块设备,元数据走KV引擎,二者分工明确。发散:本地存储引擎常把“数据路径”和“索引路径”拆开,因为两者访问模式完全不同。

查看卡片与原书出处
辅助阅读:卢曼编号

按卢曼编号阅读

点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。

  • 展开或收起下级: 244 冷热数据分层降低总体存储成本 路径上下文 Ceph分布式存储学习指南 (云计算与虚拟化技术丛书) · Ceph性能调优和基准测试 理解等级:未标注
  • 展开或收起下级: 602 顺序写加PageCache 主题成员 RocketMQ分布式消息中间件:核心原理与最佳实践 2020 · Broker存储机制 理解等级:未标注
    • 602.a 直接内存读写分离 主题成员 RocketMQ分布式消息中间件:核心原理与最佳实践 2020 · Broker存储机制 理解等级:未标注
    • 602.c 两种索引两种访问 主题成员 RocketMQ分布式消息中间件:核心原理与最佳实践 2020 · Broker存储机制 理解等级:未标注
    • 602.d 过期删除双重触发 主题成员 RocketMQ分布式消息中间件:核心原理与最佳实践 2020 · Broker存储机制 理解等级:未标注
  • 展开或收起下级: 603 OP主题对账回查 主题成员 RocketMQ分布式消息中间件:核心原理与最佳实践 2020 · RocketMQ特性——事务消息与延迟消息机制 理解等级:未标注
    • 603.b 投递时间预算进索引 主题成员 RocketMQ分布式消息中间件:核心原理与最佳实践 2020 · RocketMQ特性——事务消息与延迟消息机制 理解等级:未标注
  • 展开或收起下级: 607 Push与Pull边界 路径上下文 RocketMQ实战与原理解析 (云栖社区系列) · 用适合的方式发送和接收消息 理解等级:未标注
    • 607.c 事务消息伤顺序写 主题成员 RocketMQ实战与原理解析 (云栖社区系列) · 用适合的方式发送和接收消息 理解等级:未标注
  • 展开或收起下级: 609 顺序写定吞吐 主题成员 RocketMQ实战与原理解析 (云栖社区系列) · 消息队列的核心机制 理解等级:未标注
    • 609.a CommitLog作物理账本 主题成员 RocketMQ实战与原理解析 (云栖社区系列) · 消息队列的核心机制 理解等级:未标注
  • 展开或收起下级: 1144 FTL的定义 路径上下文 深入浅出SSD:固态存储核心技术、原理与实战 · SSD核心技术:FTL 理解等级:未标注
    • 1144.b 映射表是索引 主题成员 深入浅出SSD:固态存储核心技术、原理与实战 · SSD核心技术:FTL 理解等级:未标注
  • 展开或收起下级: 1719 宽表本质是有序KV 路径上下文 分布式系统与一致性 · 第4章 Google的BigTable系统 理解等级:未标注
  • 展开或收起下级: 1770 布隆过滤器 主题成员 大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构 理解等级:中级
    • 1770.a SkipList随机索引 主题成员 大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构 理解等级:中级
    • 1770.b LSM写读取舍 主题成员 大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构 理解等级:中级
    • 1770.c Merkle定位差异 主题成员 大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构 理解等级:中级
    • 1770.d 压缩换传输 主题成员 大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构 理解等级:中级
    • 1770.e Cuckoo驱逐冲突 主题成员 大数据日知录_架构与算法 · 第3章 大数据常用的算法与数据结构 理解等级:中级
  • 展开或收起下级: 1788 服务层只服务视图 路径上下文 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 服务层概述 理解等级:未标注
    • 展开或收起下级: 1788.a 预计算的取舍 路径上下文 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 服务层概述 理解等级:未标注
      • 1788.a.1 多粒度桶减少范围读取 主题成员 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法 理解等级:中级
      • 1788.a.3 共置排序数据以扫描代替寻道 主题成员 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 服务层概述 理解等级:中级
  • 展开或收起下级: 2009 B+树容量依赖假设 主题成员 软件架构设计_大型网站技术架构与业务架构融合之道 · 数据库 理解等级:未标注
    • 2009.c 二级索引可能需要回表 主题成员 软件架构设计_大型网站技术架构与业务架构融合之道 · 数据库 理解等级:中级
  • 展开或收起下级: 2011 WAL的本质 路径上下文 软件架构设计_大型网站技术架构与业务架构融合之道 · 数据库 理解等级:未标注
    • 2011.e LSM树替代随机写 主题成员 软件架构设计_大型网站技术架构与业务架构融合之道 · 高并发问题 理解等级:未标注
  • 展开或收起下级: 2280 故障不同于失效 路径上下文 数据密集型应用系统设计 · 可靠性、可伸缩性、可维护性 理解等级:未标注
    • 展开或收起下级: 2280.j 索引以写入换读取 主题成员 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
      • 2280.j.1 哈希索引与段压缩 主题成员 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
      • 2280.j.2 SSTable的排序收益 主题成员 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
      • 2280.j.3 LSM树与预写日志 主题成员 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
      • 2280.j.4 布隆过滤器省磁盘读 主题成员 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
      • 2280.j.5 B树与页面结构 主题成员 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
      • 2280.j.6 B树与LSM树的权衡 主题成员 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
      • 2280.j.7 堆文件聚簇与覆盖索引 主题成员 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
      • 2280.j.8 多列查询与多维索引 主题成员 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
      • 展开或收起下级: 2280.j.11 列式存储 路径上下文 数据密集型应用系统设计 · 存储与检索 理解等级:未标注
        • 2280.j.11.a 列存的排序与写入 主题成员 数据密集型应用系统设计 · 第三章:存储与检索 理解等级:高级
  • 展开或收起下级: 2281 数据管理三阶段演进 路径上下文 数据库原理(微课版) (郭玉彬,宋歌,边山) · 绪论 理解等级:未标注
    • 展开或收起下级: 2281.l 表空间的逻辑存储结构 主题成员 数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引 理解等级:未标注
      • 2281.l.1 三种表组织方式 主题成员 数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引 理解等级:未标注
      • 2281.l.2 存储引擎的四模块 主题成员 数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引 理解等级:未标注
      • 2281.l.3 聚簇索引与索引类型 主题成员 数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引 理解等级:未标注
      • 2281.l.4 B树索引结构与效率 主题成员 数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引 理解等级:未标注
      • 2281.l.5 B+树的叶子链表 主题成员 数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引 理解等级:未标注
      • 2281.l.6 哈希索引的冲突消解 主题成员 数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引 理解等级:未标注
      • 2281.l.7 位图R树与倒排索引 主题成员 数据库原理(微课版) (郭玉彬,宋歌,边山) · 数据库存储与索引 理解等级:未标注
  • 展开或收起下级: 2343 热数据受内存约束 路径上下文 App后台开发运维和架构实践 · MongoDB——App后台新兴的数据库 理解等级:未标注
    • 2343.d 位置查询用空间索引 主题成员 App后台开发运维和架构实践 · MongoDB——App后台新兴的数据库 理解等级:未标注
  • 展开或收起下级: 2344 心跳处理半开 路径上下文 App后台开发运维和架构实践 · App后台架构剖析 理解等级:未标注
    • 2344.d 地理邻域要补边 主题成员 App后台开发运维和架构实践 · App后台架构剖析 理解等级:未标注
  • 展开或收起下级: 2350 BlueStore直管设备 主题成员 Ceph之RADOS设计原理与实现 · 高效本地对象存储引擎——BlueStore 理解等级:未标注
    • 2350.a RocksDB管元数据 主题成员 Ceph之RADOS设计原理与实现 · 高效本地对象存储引擎——BlueStore 理解等级:未标注
    • 2350.b BlueFS服务元数据 主题成员 Ceph之RADOS设计原理与实现 · 高效本地对象存储引擎——BlueStore 理解等级:未标注
  • 展开或收起下级: 2476 三层存储文件的职责分工 主题成员 RocketMQ技术内幕 RocketMQ架构设计与实现原理 · RocketMQ消息存储 理解等级:未标注
    • 2476.a 组提交读写双容器分离设计 主题成员 RocketMQ技术内幕 RocketMQ架构设计与实现原理 · RocketMQ消息存储 理解等级:未标注
    • 2476.b 三级指针管理数据安全边界 主题成员 RocketMQ技术内幕 RocketMQ架构设计与实现原理 · RocketMQ消息存储 理解等级:未标注
    • 2476.d 过期文件删除的双触发机制 主题成员 RocketMQ技术内幕 RocketMQ架构设计与实现原理 · RocketMQ消息存储 理解等级:未标注
    • 2476.f 堆外内存读写分离 主题成员 RocketMQ技术内幕 RocketMQ架构设计与实现原理 · RocketMQ消息存储 理解等级:未标注
    • 2476.g 内存映射借用页缓存 主题成员 RocketMQ技术内幕 RocketMQ架构设计与实现原理 · RocketMQ消息存储 理解等级:未标注
  • 展开或收起下级: 2480 复制组内主从切换维持集群写能力 路径上下文 RocketMQ技术内幕 RocketMQ架构设计与实现原理 · RocketMQ主从切换 理解等级:未标注
    • 2480.d 返回body偏移保兼容 主题成员 RocketMQ技术内幕 RocketMQ架构设计与实现原理 · RocketMQ主从切换 理解等级:未标注
  • 展开或收起下级: 2542 伸缩延迟三段论 路径上下文 Serverless核心技术和大规模实践 · FaaS弹性伸缩 理解等级:未标注
    • 2542.d 内存指标系统 主题成员 Serverless核心技术和大规模实践 · FaaS弹性伸缩 理解等级:未标注
  • 展开或收起下级: 2633 协程分层 路径上下文 万亿级流量转发 BFE核心技术与实现 2021 · BFE的基础实现 理解等级:未标注
    • 2633.d 域名Trie表 主题成员 万亿级流量转发 BFE核心技术与实现 2021 · BFE的基础实现 理解等级:未标注
  • 展开或收起下级: 2774 HDFS三副本放置 路径上下文 企业大数据系统构建实战_技术、架构、实施与应用 (大数据技术丛书) · 大数据技术介绍 理解等级:未标注
    • 2774.b HBase追加后台合并 主题成员 企业大数据系统构建实战_技术、架构、实施与应用 (大数据技术丛书) · 大数据技术介绍 理解等级:未标注
    • 2774.g 倒排索引反向查找 主题成员 企业大数据系统构建实战_技术、架构、实施与应用 (大数据技术丛书) · 大数据技术介绍 理解等级:未标注
  • 展开或收起下级: 2804 HBase源于Bigtable 路径上下文 分布式实时计算框架原理及实践案例 · NoSQL:MongoDB3.0和HBase1.0 理解等级:未标注
    • 2804.b LSM写快读慢 主题成员 分布式实时计算框架原理及实践案例 · NoSQL:MongoDB3.0和HBase1.0 理解等级:未标注
  • 2811 单例检查去重 主题成员 分布式对象存储——原理、架构及Go语言实现 · 数据校验和去重 理解等级:未标注
  • 展开或收起下级: 2856 监控是反馈 路径上下文 分布式架构原理与实践 · 指标与监控 理解等级:未标注
    • 2856.j LSM适合写入 主题成员 分布式架构原理与实践 · 指标与监控 理解等级:未标注
  • 展开或收起下级: 2910 哈希安全边界 路径上下文 区块链架构与实现:Cosmos详解 · 密码学算法 理解等级:未标注
    • 2910.a Merkle状态指纹 主题成员 区块链架构与实现:Cosmos详解 · 密码学算法 理解等级:未标注
    • 2910.b Merkle域隔离 主题成员 区块链架构与实现:Cosmos详解 · 密码学算法 理解等级:未标注
  • 展开或收起下级: 2914 AppModule契约 路径上下文 区块链架构与实现:Cosmos详解 · Cosmos-SDK的架构设计 理解等级:未标注
    • 2914.c IAVL版本化 主题成员 区块链架构与实现:Cosmos详解 · Cosmos-SDK的架构设计 理解等级:未标注
  • 展开或收起下级: 3622 链表顺序来自节点指针 路径上下文 Introduction to Algorithms, Fourth Edition · 第10章 基本数据结构 理解等级:初级
  • 展开或收起下级: 3633 B树降低磁盘访问层数 主题成员 Introduction to Algorithms, Fourth Edition · 第五部分 高级数据结构 理解等级:中级
    • 展开或收起下级: 3633.a B树为外存访问而平衡 主题成员 Introduction to Algorithms, Fourth Edition · 第18章 B树 理解等级:中级
      • 展开或收起下级: 3633.a.3 外存算法分开计量IO 路径上下文 Introduction to Algorithms, Fourth Edition · 第18章 B树 理解等级:高级
        • 3633.a.3.a B树查找区分IO与CPU 主题成员 Introduction to Algorithms, Fourth Edition · 第18章 B树 理解等级:高级
      • 3633.a.5 节点大小决定B树分支度 主题成员 Introduction to Algorithms, Fourth Edition · 第18章 B树 理解等级:高级
      • 3633.a.6 B加树把附属信息放叶子 主题成员 Introduction to Algorithms, Fourth Edition · 第18章 B树 理解等级:中级
      • 展开或收起下级: 3633.a.8 最小度约束节点键数 路径上下文 Introduction to Algorithms, Fourth Edition · 第18章 B树 理解等级:中级
        • 3633.a.8.a B树高度由最小分支约束 主题成员 Introduction to Algorithms, Fourth Edition · 第18章 B树 理解等级:高级
        • 展开或收起下级: 3633.a.8.c B树删除需防节点过稀 路径上下文 Introduction to Algorithms, Fourth Edition · 第18章 B树 理解等级:中级
          • 3633.a.8.c.5 B树删除按树高计IO 主题成员 Introduction to Algorithms, Fourth Edition · 第18章 B树 理解等级:高级
  • 4439 布隆过滤减少无效查盘 主题成员 System Design Interview – An insiders guide, Second Edition · 键值存储 理解等级:高级
  • 4996 双向索引服务不同查询 主题成员 从Paxos到Zookeeper:分布式一致性原理与实践 · 技术内幕:系统模型与客户端 理解等级:中级
  • 5055 数据树用路径索引节点 主题成员 从Paxos到Zookeeper:分布式一致性原理与实践 · 技术内幕:系统模型与客户端 理解等级:中级
  • 5056 临时节点另按会话索引 主题成员 从Paxos到Zookeeper:分布式一致性原理与实践 · 技术内幕:系统模型与客户端 理解等级:中级

未编号或编号待整理

来源书籍

来源书籍

Ceph分布式存储实战

分布式存储产品实战类

Skill 版本:v1

书籍类型:未标注

清单覆盖 8/8

39 张卡片

来源书籍

分布式系统与一致性

分布式系统类

Skill 版本:v23

书籍类型:经典原理

清单覆盖 4/4

133 张卡片

主题索引

分布式存储与复制

比较 GFS、HDFS、BigTable、MongoDB、RabbitMQ 等系统的租约、写确认、副本同步、选主与脑裂处理。

501 张卡片 · 64 本书

主题索引

指标与监控

时序模型与拉推采集、黄金指标与分位、探针与 APM、容量与负载、监控分层。

382 张卡片 · 58 本书

主题索引

时空效率与复杂度分析

比较渐近复杂度、摊销分析、基准测试以及以抽象换空间、局部性等时间与空间效率的权衡。

333 张卡片 · 17 本书

主题索引

分布式事务与一致性

比较内部与外部一致性、XA/2PC/3PC、CAP 与 BASE,以及可靠事件队列、TCC、SAGA、AT 等柔性事务方案。

308 张卡片 · 61 本书

主题索引

服务发现与网关

比较服务发现范式、注册中心的 CAP 取舍与实现路线、网关与 BFF,以及地域与区域的流量边界。

286 张卡片 · 70 本书

主题索引

并发任务与同步原语

比较线程/任务抽象、异步结果传递、原子与同步手段的语义差异和生命周期约束。

215 张卡片 · 41 本书