B-Link Tree总结 B-Link Tree相比传统的B+树，主要有两个特点： 内页有一个指向右兄弟页的指针。 内页有一个high key，大于当前节点以及所有子节点中最大的key。 这两个特点，结合B-Link Tree的搜索、封锁、分裂方式，可以极大地降低并发冲突。主要特征总结如下： 搜索 搜索B树时，对非叶子节点只会上S锁，仅叶子节点可能上X锁。 搜索...

PostgreSQL B树搜索 PG使用B-Link Tree作为存储结构，本文分析其搜索流程 _bt_first第一次搜索B树，先处理key，处理并行扫描，决定比较模式(<, <=, =, >, >=)，扫描顺序(向前或向后)，初始化scankey，最终进入_bt_search搜索key所在页，然后调用_bt_binsrch二分搜索页中记录。 _bt_firs...

PostgreSQL B树插入 PG使用B-Link Tree作为存储结构，本文分析其插入流程 _bt_doinsert将一个tuple插入到B树： _bt_doinsert { // 构造scan key _bt_mkscankey // WRITE模式定位待插入的叶子页。路径上的节点都只会上S锁，访问孩子页后解锁，叶子节点会上X锁。搜索时会登记搜索路径到st...

MySQL字典 字典是表、索引、模式、约束等数据库对象的描述信息，需要访问时会从系统表加载到内存。 MySQL中，字典有以下几种： dict_table_t // 表 dict_col_t // 列 dict_index_t // 索引 dict_foreign_t // 外键约束

btr_pcur源码分析 MySQL对B树进行查询、插入、更新、删除等操作时，经常使用btr_pcur(Persistent B-tree Cursor)完成，本文分析btr_pcur源码。

B树源码解析 本文分析MySQL InnoDB中B树的实现，包括插入、更新、删除、搜索等。

Undo日志 undo日志有两个作用： 实现事务的隔离性。由于事务隔离级别的要求，其他事务对表的修改可能对当前事务不可见，此时当前事务需要通过undo日志拼装出最后可见的记录。 保证数据的一致性和正确性。事务回滚时，需要通过undo日志重做对表的操作。 MySQL中，redo日志是mtr实现的，undo日志则是trx实现的。 未完待续

purge 数据库系统中，事务删除记录时，不会立即从B树中删除，而是打上删除标记。这样做有以下两个原因： 实现事务的隔离性。事务在删除记录并提交后，其他事务可能需要访问这条记录，只有当记录对所有活动事务都不可见时，才可以从B树中删除。打上删除标记后，其他事务通过key或索引扫描可以定位到这条记录，判断删除对当前事务不可见、或通过记录上rollptr找到undo日志拼装出最...

Mini Transaction MySQL InnoDB中，mtr是一个非常重要的模块，主要控制redo日志和数据页锁。 redo日志 redo日志即数据库的预写日志（WAL），有以下两个作用： 提高事务的提交速度。事务修改的数据页在磁盘上极有可能是不连续的，刷盘将会是随机IO，效率较差。事务会将所有对数据页的修改记录成redo日志，提交时只需保证这些redo日志刷...