技巧💡
access method ,是我们对数据库数据进行读或者写的方式。 数据结构无处不在。
- 数据组织：如何将这些数据结构合理地放入 memory/pages 中，以及为了支持更高效的访问，应当存储哪些信息。
常用的数据存储，我们一般分为2类。
- Tuple-oriented存数据，使用In-place update structure就地更新结构，如B+树。是直接覆盖旧记录来存储更新内容。
- Log-structured存日志，使用out-place-update-structure异地更新结构，会将更新的内容存到到新的位置，而不是覆盖。
| 流派 | 主要特点 | 基本思想 | 代表 |
|---|---|---|---|
| log-structured 流 | 只允许追加，所有修改都表现为文件的追加和文件整体增删 | 变随机写为顺序写 | Bitcask、LevelDB、RocksDB、Cassandra、Lucene |
| update-in-place 流 | 以页（page）为粒度对磁盘数据进行修改 | 面向页、查找树 | B 族树，所有主流关系型数据库和一些非关系型数据库 |
结构
| 结构 | 主义特点 | 基本思想 | 主要问题 | 优化思路 |
|---|---|---|---|---|
| 哈希表 | 主要适用于pagetable,自适应hash等 | 通过hash函数，查找很快 | 不支持范围查询。如mysiam存储引擎，hash冲突 | 解决hash冲突，如拉链法等 |
| Trees B树 | 就地更新数据，直接覆盖。以页的力度对磁盘进行修改.主流关系型数据库的选择 | 增加读性能，已经是排序好的最好数据。 | 写的时候可能会存在页合并，页分裂等情况。并发控制不好 | B link树，解决B+树并发控制自下而上的问题 |
| LSM树 | Log-structured的代表，数据通过日志的方式进行存储。KV数据库、大数据相关的数据库的选择.LSM-Tree 并不是一种严格的树结构，而是一种内存+磁盘的多层存储结构。HBase、LevelDB、RocksDB这些 NoSQL 存储都使用了 LSM-Tree | 增加写性能，通过随机写变顺序写(写日志很快) | 读的时候，获取最新数据需要根据日志进行推演 | 1. 优化SSTABLE查找 Bloom过滤器2. 层级SSTABLE，进行compaction合并 |
资料
DDIA 读书笔记（三）：B-Tree 和 LSM-Tree | 木鸟杂记