外部存储
数据库管理系统 DBMS 是现代应用中不可或缺的一部分, 其中一个重要原因是其隐藏了外存管理的细节, 并为应用层提供了高效, 易用的数据检索 Retrieval 与持久化 Persistence 功能.
外存具有容量大, 成本低, 断电非易失等优点, 但同时也存在寻址慢, 访问粒度粗的问题:
内存寻址速度快(ns 级), 寻址单位小(byte)
外存寻址速度慢(ms 级), 寻址单位大(>=4kb)
数据库的读写性能取决于外存访问效率, 而优化外存访问的手段有:
减少外存访问次数: 借助写缓冲 Buffer, 读缓存 Cache 的方式, 将热点数据临时存储在内存, 避免频繁的外存访问
避免随机寻址: 使用预写日志 WAL 对写操作进行优化, 将随机写操作简化为顺序的追加操作
单次读取尽可能多的数据: 使用高密度的外存索引 Index 来组织数据, 通过有序性提高检索效率
预写日志
预写日志系统 WALWrite-Ahead Logging 是一种用于提高数据库写性能的常见手段, 被广泛应用于持久化数据库中.
数据库中的状态可以分为两部分:
WAL 日志: 所有对数据库的变更都先写入这个日志, 并在事务提交时进行持久化, 防止已提交数据丢失, 已提交的日志数据会被定期清理
DB 文件: 包含所有已经交的数据, 索引信息, 数据长期存在不会消失
WAL 的核心思想是 日志先行 :
写数据时, 变更操作首先追加到 WAL 日志末尾, WAL 会将数据顺序刷到磁盘(提交成功). 异步线程会消费 WAL 中的变更消息(类似于队列), 将应用变更到 DB 文件中并重置 WAL
读数据时, 需要同时读取 WAL 与 DB 中的数据, 并将两者合并生成最新的记录
由于追加 WAL 是顺序的, 可以将随机的磁盘 IO 转换为顺序的磁盘 IO, 减少磁盘巡道时间, 从而能够更有效地提升了磁盘的吞吐量.
数据库重启过程中会检查 WAL 日志, 任何尚未附加到 DB 数据页的记录都将从日志记录中重放, 每次提交事务时不再需要 (为了保证数据安全) 把数据页冲刷到磁盘, 有效地提升了事务吞吐量.
WAL 只允许在尾部追加数据 Append-Only , 不允许修改日志记录. 这种不变性 Immutability 有利于并发控制: 删改数据只能通过追加新的日志实现, 因此修改前无需对数据加锁, 直接在日志末尾追加新的记录即可.
然而 WAL 的体积也不可能无限增长, 系统需要周期性周期性的清理无用的日志记录, 减少文件碎片, 释放磁盘空间.
索引
索引是一种附加的数据结构, 以牺牲空间和写入速度为代价, 换取更快的检索速度. 最常用的索引结构莫过于 Hash 与 Tree:
Hash
维护方便, 单个 key 的随机查找速度极快, 一般都是常量级的 O(1)
无法支持范围查找, 随着记录的增长, 哈希冲突率上升, 导致查找速度下降
整个索引需要保证能够放入内存, 否则就无法发挥其速度优势
Tree
支持范围查找, 查找速度稳定, 二叉平衡树可以保证 O(log2n)
维护成本较高, 插入数据时需要重新平衡树, 每个节点的需要额外的指针存储空间
大数据量的情况下查找性能比较稳定, 具有多种变种算法可以适配各种应用场景
由于数据库需要管理海量的数据, 因此 Tree 便成为外存索引的不二之选.
下面介绍其中最具代表性两类索引结构: B-Tree 与 LSM-Tree
B-Tree
最基础的 Tree 莫过于二叉查找树. 其查找数据的方式, 就是从根节点开始逐层向下遍历, 直到找到目标节点. 但是当数据量比较大的时候, 会有以下问题:
节点之间的地址不连续, 每次在节点之间的跳转访问时, 都要进行寻址, 访问效率不高
最坏情况下的访问效率取决于树的高度, 当数据量大时, 即便是平衡树, 其高度也很可观
B-Tree 是一种用于处理海量数据的平衡多路查找树, 其主要改进是对二叉树中间节点进行了合并, 通过平衡算法和分叉因子 b, 可以将树高度控制在 logbn 的级别, 对外存访问更为友好:
每个节点包含尽可能多的数据, 可以一次读出大量的数据, 减少对外存的访问次数
有效地降低了整棵树的高度, 在大数据量的情况下能够保证较少的访问次数
这意味着: 只需要很少的磁盘 IO, 就能够对大量的数据进行高效的查找操作.
B-Tree 在作为外存索引使用时:
根节点会常驻内存, 其余节点存储在磁盘上, 从而能够减少一次磁盘 IO
按照页来组织数据, 每个节点大小需对应一个完整的页(磁盘 IO 的基本单位是物理块 block, 操作系统使用逻辑页 page 管理应用程序的地址映射)
为了保证数据的安全性, 在对索引数据进行修改前要先写 WAL, 因此每次写操作会造成至少两次磁盘写(忽略写缓存)
写入的 Key 如果是随机或不连续的, 可能会造成索引节点的多次分裂, 影响写入的效率(写放大效应)
在多次修改, 删除操作之后, 索引文件中会产生比较多的空洞, 造成磁盘空间的浪费, 并且会影响读性能(需要定期重建索引)
B+Tree 是对 B-Tree 的进一步改进: 将 Key 与 Value 进行分离, 非叶节点只保存 Key, 所有 Value 下沉到叶子节点.
每个中间节点可以容纳更多的 Key, 进一步提高了中间节点的密度, 在相同的数据量下, 树的高度要比 B-Tree 更低.
来源: http://www.bubuko.com/infodetail-3655620.html