Likanug // lab
返回文章列表

文章

读书笔记

Build Your Own Database from Scratch - 2

Indexing Data Structures

#Go#Database#算法#数据结构
目录
  1. 2. 数据结构与索引示例
  2. 3. 列式存储加速全表扫描的原理
  3. 2、Hashtables
  4. 2. 渐进式重哈希（Progressive Rehashing）
  5. 3. 哈希表扩容触发条件
  6. 3、Sorted arrays
  7. 既然排除了哈希表，我们便从最简单的有序数据结构——排序数组（Sorted Array） 开始。在排序数组上可进行 𝑂(log 𝑁) 时间复杂度的二分查找。对于字符串等变长数据（如键值对），可通过指针数组（或偏移量数组） 实现二分查找。但排序数组的更新（增删改）时间复杂度为 𝑂(𝑁)（无论是否原地操作），因此并不实用。不过，其设计思想可延伸至其他可更新数据结构。
  8. 1、 排序数组的局限性及改进方向
  9. 2、从嵌套排序数组到 B+树
  10. 3、LSM树（日志结构合并树）的写入优化
  11. 对比：B+树 vs. LSM树
  12. 4、B-tree
  13. 1、通过降低树高减少随机访(Reducing random access with shorter trees)
  14. 2、IO in the unit of pages
  15. 虽然你可以从文件的任意偏移处读取任意数量的字节，但磁盘的工作方式并非如此。磁盘I/O的基本单位不是字节，而是扇区——在老式HDD上，扇区是512字节的连续块。 然而，磁盘扇区并不是应用程序关心的问题，因为常规的文件I/O并不会直接与磁盘交互。操作系统会将磁盘的读写操作缓存/缓冲在页缓存中，该缓存由称为页面(pages)的4K字节内存块组成。 无论如何，I/O总存在一个最小单位。数据库也可以定义它们自己的I/O单位（也称为页面(page)），这个单位可以大于操作系统的页面。 最小I/O单位意味着树节点应以该单位的整数倍进行分配；如果只使用一半，就等于浪费了一半的I/O。另一个反对采用小n的理由！
  16. 3、The B+tree variant
  17. 4、Data structure space overhead
  18. 二叉树不切实际的另一原因：二叉树的另一大缺陷在于其指针数量过多。每个键至少需要父节点的一个指针指向它，而B+树的叶子节点中多个键可共享一个父节点指针。此外，B+树的叶子节点可通过紧凑存储格式或键值压缩进一步减少空间占用。
  19. 5、日志结构存储(Log-structed storage)
  20. 2、通过多级结构降低写放大效应(Reduce write amplification with multiple levels)
  21. LSM-tree indexes
  22. LSM-tree queries
  23. Real-world LSM-tree: SSTable, MemTable and log
  24. 1. SSTable（Sorted String Table）的分割设计
  25. 2. 第一层的日志化设计（Log-Structured Level 1）
  26. 3. MemTable 的设计权衡
  27. 4. 实际系统优化案例（LevelDB/RocksDB）
  28. 总结
# Indexing Data Structures ## 1、Types of queries 大多数 SQL 查询可归纳为三种类型： 1. **全表扫描（Scan）**：遍历整个数据集（不使用索引）。 2. **点查询（Point Query）**：通过特定键值查询索引。 3. **范围查询（Range Query）**：通过范围条件查询索引（索引需有序）。 尽管可通过列式存储（Column-based Storage）等技术加速全表扫描，但其时间复杂度始终为 **𝑂(𝑁)**。因此，我们更关注**基于数据结构实现 𝑂(log 𝑁) 复杂度**的查询优化。 **范围查询的两个阶段**： 1. **定位（Seek）**：找到起始键值。 2. **遍历（Iterate）**：按排序顺序查找前驱/后继键值。 **点查询**本质上只需“定位”阶段，无需遍历。由此可见，**有序数据结构**是实现高效查询的关键基础。 **关键技术解析与扩展：** ### **1. 查询类型对比与优化策略** 1. **全表扫描（Scan）** ```sql -- 无索引时，查询需扫描所有行 SELECT * FROM users WHERE name LIKE '%John%'; ``` - **行为**：逐行检查 **`name`** 字段是否包含 "John"。 - **代价**：𝑂(𝑁) 时间复杂度（𝑁 为总行数）。 2. **点查询（Point Query）** ```sql -- 通过索引快速定位单条记录（如哈希索引） SELECT * FROM users WHERE id = 100; ``` - **行为**：直接跳转到 **`id=100`** 的位置（𝑂(1) 或 𝑂(log 𝑁)）。 3. **范围查询（Range Query）** ```sql -- 利用有序索引（如B+树）加速范围查找 SELECT * FROM orders WHERE amount BETWEEN 100 AND 500; ``` - **行为**：先定位到 **`amount=100`**，然后顺序扫描至 **`amount=500`**（𝑂(log 𝑁 + 𝑀)，𝑀 为匹配行数）。
**查询类型****时间复杂度****典型优化方案****适用场景**
**全表扫描**𝑂(𝑁)列式存储、向量化处理、并行扫描聚合分析（如 **`COUNT(*)`**）
**点查询**𝑂(1) 或 𝑂(log 𝑁)哈希索引（Hash Index）、B+树索引主键查询（如 **`WHERE id = 100`**）
**范围查询**𝑂(log 𝑁 + 𝑀)B+树索引、LSM-Tree（日志结构合并树）范围过滤（如 **`WHERE age BETWEEN 20 AND 30`**）

注： - 𝑀 表示范围内匹配的记录数。 - B+树因其有序性和平衡性，能高效支持点查询和范围查询。

2. 数据结构与索引示例#

B+树索引（范围查询）

-- 创建支持范围查询的索引
CREATE INDEX idx_age ON users(age);
-- 范围查询示例
SELECT * FROM users WHERE age >= 20 AND age <= 30;
  • 定位（Seek）：快速找到 age=20 的起始位置（时间复杂度 𝑂(log 𝑁)）。
  • 遍历（Iterate）：沿叶子节点链表顺序扫描至 age=30（时间复杂度 𝑂(𝑀)）。

哈希索引（点查询）

-- 哈希索引通常隐式用于主键查询
SELECT * FROM users WHERE id = 100;
  • 直接通过哈希函数定位记录（理想情况下 𝑂(1)）。

3. 列式存储加速全表扫描的原理#

  • 存储方式：按列而非行存储数据。
  • 优势：
    • 压缩效率高：同列数据类型一致，易于压缩（如 RLE、字典编码）。
    • 向量化处理：利用 SIMD 指令批量处理列数据。
  • 适用场景：OLAP（分析型查询，如 SUM(revenue) GROUP BY region）。

总结：理解查询类型及其底层数据结构，是优化数据库性能的关键。通过合理设计索引（如 B+树、哈希表）和存储模型（行存 vs. 列存），可显著提升系统效率。

2、Hashtables#