November 3, 2022
1. B+ Tree # B+ Tree 是平衡搜索树的一种，是为了磁盘搜索而生的。它一般将磁盘块大小作为叶子节点的大小，方便数据读取，插入，原地更新等。B+ Tree 的查询/插入/删除 的时间复杂度都是 O(LogN)
2. LSM Tree # LSM Tree 的核心思想是将离散的随机读写请求转换成批量的顺序读写请求。它采用的是 Append Only 方式对数据插入，更新（无法原地更新）。查询顺序为如下步骤。
Memtable -> Frozen Memtable -> L0 -> L1 -> ··· -> LN 3. LSM Tree Compaction # Compaction 实际是数据的重新整合，实质是多路归并排序，主要作用是减少 SSTable 的数量，提升查询性能。但是它资源耗费比较高（IO：需要大量的读取与写入操作；CPU：涉及 checksum 计算，rowkey 比较；性能抖动）
3.1 Amplification # 名词 英文 说明 读放大 Read Amplification 本次扫描的数据量/实际返回的数据量 写放大 Write Amplification 磁盘写入的数据量/实际的数据量 空间放大 Space Amplification 存储的数据量/实际的数据量 3.2 Compaction Strategy # 不同的 Compaction 策略是对写放大、空间放大、读放大的一个权衡。
...
July 18, 2022
LevelDB 事务
...
July 10, 2022
在 Minor Compaction 完成的时候，会对新生成的 version 计算一次 compaction_level_ 和 compaction_score_。这两个参数决定了当前 version 的 是否需要做 Major Compaction。
...
June 30, 2022
Minor Compaction 流程
...
June 29, 2022
1. latch # 是内存结构中的一种轻量级的锁，在 MySQL 数据库中，latch 是用于保护内存中 List Page 完整性的锁结构，latch 可以分为有 mutex、SX rw-lock（spin lock），SX rw-lock 是 MySQL 5.7 的新特性，针对 Page 粒度加的内存锁，有助于提升索引访问效率（针对索引更新的模式）。
2. Lock # Gap Lock（间隙锁）锁住的区间均为开区间，间隙锁之间是兼容的，即两个事务可以同时持有包含共同间隙范围的间隙锁，并不存在互斥关系 Next-Key Lock（临键锁）锁住的区间除了 supremum 伪记录所在区间是开区间外，其余区间均为左开右闭区间；如果一个事务获取了 X 行的 next-key lock，那么另外一个事务在获取相同范围的 X 行的 next-key lock 时，是会被阻塞的 2.1 锁与事务隔离级别 # Isolation/Lock Lock Mode + Lock Type Rec Lock Type Read uncommitted Read commited LOCK_IX + TABLE_LOCK LOCK_X + ROW_LOCK LOCK_REC_NOT_GAP Repeatable read LOCK_IX + TABLE_LOCK LOCK_X + ROW_LOCK LOCK_REC_NOT_GAP or LOCK_GAP or LOCK_ORDINARY Serializable 3.
...
June 24, 2022
容器 底层数据结构 时间复杂度 有无序 可否重复 其他 array 数组 随机读改 O(1) 无序 可重复 支持随机访问 vector 数组 随机读改、尾部插入、尾部删除 O(1)；头部插入、头部删除 O(n) 无序 可重复 支持随机访问 deque 双端队列 头尾插入、头尾删除 O(1) 无序 可重复 一个中央控制器 + 多个缓冲区，支持首尾快速增删，支持随机访问 forward_list 单向链表 插入、删除 O(1) 无序 可重复 不支持随机访问 list 双向链表 插入、删除 O(1) 无序 可重复 不支持随机访问 stack deque / list 顶部插入、顶部删除 O(1) 无序 可重复 deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时 queue deque / list 尾部插入、头部删除 O(1) 无序 可重复 deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时 priority_queue vector + max-heap 插入、删除 O(log2n) 有序 可重复 vector 容器+heap 处理规则 set 红黑树 插入、删除、查找 O(log2n) 有序 不可重复 multiset 红黑树 插入、删除、查找 O(log2n) 有序 可重复 map 红黑树 插入、删除、查找 O(log2n) 有序 不可重复 multimap 红黑树 插入、删除、查找 O(log2n) 有序 可重复 unordered_set 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复 unordered_multiset 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复 unordered_map 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复 unordered_multimap 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复
June 21, 2022
trait 并不是 C++ 的关键字之类的，属于 C++ 的一种“机制”，或者说 C++ 特有的一种编程小技巧。
...
June 20, 2022
STL 是 1979 年诞生，1998 年加入 cpp 标准库。C11 出来之前 boost 库是常见的智能指针库，c11 有自己的智能指针。且有多个 STL 版本，如 SGI STL，GNU STL。
...
June 10, 2022
Open 流程
...
May 30, 2022
Endian-neutral encoding:
* Fixed-length numbers are encoded with least-significant byte first
* In addition we support variable length "varint" encoding
* Strings are encoded prefixed by their length in varint format
-- util/coding.h