15445问题¶

buffer pool¶

pin_count多少个进程在用

页的管理-》容量有限，有根据的把原来的页替换掉

追踪页的使用

map（查找的效率是O1）+ linkedlist (删除和增加的效率是O1) ->整体O1

LRU:是用来记录每一个page的id，page id

victim : frame_id_t * parameter out 返回多个值，每次把least 删除，并返回id

pin 找到节点，从lru删除

unpin 没有人使用的时候可以安全删除

size lru记录多少页

为什么要自己做缓存池，操作系统不是有pagecache吗？你这个缓存池的作用？为什么需要这个？
Buffer Pool的目的是为了缓存部分Page从而提高Scan的效率，同时通过尽可能地匹配工作负载的淘汰策略，来提高缓存命中率，进而提高DBMS的查询性能。
是缓存池，主要用于数据库底层的内存管理，包括控制 Page 的进出，分配多大的内存空间。
memory一个是disk，disk访问速度很慢，memory访问速度快（但是存储量小），更快访问速度
是为了数据库能有比 OS 更加全面的内存管理机制而实现的底层数据结构(Oracle / PostgreSQL 中均有用到)，最主要的是，在极端的 AP 情况下，没有缓存池支持的数据库，非常容易发生 OOM (Out Of Memory) 的问题
如果数据库没有缓存池支持，所有数据操作都需要直接与磁盘进行交互，这不仅会导致性能问题，也会因为大量的并发操作和数据处理在内存中累积，增加了发生OOM错误的风险。没有缓存机制意味着数据库不能有效地管理内存资源，容易在高负载下耗尽可用内存，导致OOM错误，进而影响系统的稳定性和可用性。
脏页管理：数据库操作中常常涉及到事务，需要对脏页（即被修改过但未写回磁盘的页面）进行管理。数据库可以通过自己的缓存池来更有效地管理这些脏页，实现事务日志、回滚等复杂的数据一致性要求。
写回策略：数据库可以控制数据的写回策略，例如，选择合适的时机批量写回脏页，减少磁盘I/O操作和提高系统的整体性能。
先查看memory,然后从disk中取
page-table: frame_id是缓存中页的id，page_id是在磁盘中具体的页的id
Free-List->LRU可以枷锁并发安全性
fetch page一定要等有空间之后哦才能找新的
pin_count现在有多少个进程在用
是否dirty，写回
newpage ->新建页free list 先找完全空闲的，然后再从lru
lock&latch 准备回滚transaction事务 latch是锁
哈希表、LRU-K淘汰策略、以及基于上述组件的Buffer Pool Manager
既然有缓存，就一定会有缓存一致性的问题。这里使用了Copy-On-Write的策略，通过标记脏页、按需刷回的方式来处理，这与OS中页缓存的管理策略类似。为了更高效地获取Page与Frame的映射关系，增加PageTable的哈希表进行辅助。
这里使用了Copy-On-Write的策略，通过标记脏页、按需刷回的方式来处理，这与OS中页缓存的管理策略类似。为了更高效地获取Page与Frame的映射关系，增加PageTable的哈希表进行辅助。
介绍一下LRU, 介绍一下其他的置换算法, lru-k 比 lru 好在哪, 说一下这个LRU－k怎么实现的,k怎么选择？依据？
LRU策略的改进版，通过设置回头看的参数K，在淘汰时选择过去K次访问中间隔最大的元素
在LRU-K中，系统跟踪每个数据项被访问的最后K次时间。只有当数据项的第K次访问发生时，才将其移到LRU列表的前端。这意味着数据项需要被访问K次才能被视为“热点数据”。
相比于普通的LRU，能够更好地应对Sequential Flooding的情况，比如说全表Scan时，很多冷数据都会被充入Cache，这会导致LRU下很多热数据被误淘汰，而在LRU-2下，这些冷数据大概率不会被访问，所以会优先淘汰掉其本身，从而提高热数据的命中率。
缓存池的更新机制为 LRU-K 缓存置换算法，相较于普通的 LRU 算法，通过增加 Timestamp 额外标签的策略，可以有效避免缓存污染的问题
对于这种情况我仍然建议先拿一把全局锁（以单个函数作为锁的粒度），保证正确性的情况下，再进行优化。
FIFO（先进先出）：最简单的页面置换算法，按照页面载入内存的先后顺序进行淘汰。容易造成频繁被访问的页面被淘汰的“Belady异常”。
LFU（最少使用频率）：淘汰在过去一段时间内被访问次数最少的页面。与LRU不同，它基于访问频率而非时间顺序。
更好的适应性：通过考虑数据项的多次访问，LRU-K能更好地识别真正的热点数据，从而减少缓存污染。
提高缓存命中率：相比LRU，LRU-K能更精确地保留那些频繁访问的数据，从而提高缓存命中率。
K的选择依赖于具体应用的数据访问模式。理想的K值能够平衡识别热点数据和维护成本之间的关系。通常，K的值需要通过实验和性能测试来确定，考虑因素包括缓存命中率、系统负载、以及数据访问的时间局部性特征。在实践中，K的值通常设置为2，以减少维护成本，同时还能有效地提高缓存性能。

B+树¶

数据库底层为什么要用B+树？B+树比B树好在哪里？哪个层数更多？
第一阶数更多，路径更短，B+树每个非叶子节点存储的键值更多，它可能会比具有相同键值数量的B树拥有更少的层数
第二个磁盘读写代价B+树更低（B树在查询的时候会把路径上的节点的数据也给扫描出来），非叶子节点只存储指针，叶子阶段存储数据
第三是B+树便于扫库和区间查询，叶子节点是一个双向链表一次性就能拿到所有数据，不用再从根节点出发
第四：查询效率b+树更加稳定：因为都是要到叶子节点上去查询，去的层级几乎一模一样，都是去叶子节点层获取，长度差不多
B+树的结构，插入查找删除操作，节点是怎么分裂合并的，b+树实现中最难的是并发和分裂，合并
单线程的只支持唯一键的B+树，实现查找、插入、删除三种操作
初始化插入：如果树是空的，则创建一个新的叶子节点作为根节点。如果树不为空，则通过 find_leaf_page 方法找到应该插入键值对的叶子页面 L。
检查叶子页面大小: 如果 �L 的大小未达到最大值 (maxsize)，则插入成功并结束。如果 �L 的大小达到 maxsize，则需要进行分裂。
分裂叶子页面: 创建一个新的叶子页面 �′L′。将 �L 中的一半键值对移到 �′L′ 中。更新父节点以包含新页面 �′L′ 的信息。
插入到父页面 (insert_in_parent):如果 �L 是根页面，则创建一个新的内部节点 �R 作为根，并让 �R 包含 �L 和 �′L′。如果 �L 不是根页面，找到 �L 的父页面 �P，并尝试在 �P 中插入新的键值对。如果 �P 的大小也达到 maxsize，则需要对 �P 进行分裂。
查找：查找一个给定的键值key在B+树中的过程涉及从根节点开始，逐层向下寻找，直到找到相应的叶子节点。在每个非叶子节点上，你需要找到第一个大于等于给定键值的关键字，然后遍历到该关键字对应的子树中去。重复这个过程直到达到叶子节点。一旦到达叶子节点，就可以直接在该节点上进行查找，确定键值是否存在。
当页的大小 < minsize时，可以选择向左/向右借或者合并，先往左边或者先往右边，或者先借还是先合并顺序都不重要。只要保证满足发生借或者合并后，节点与兄弟节点大小满足大于等于minsize即可。假设我们找到节点的sibling , 如果sibling size > minsize ，那么直接借一个，不会影响父节点的大小。
如果left sibling size = minsize, 合并两个节点，总是删除合并节点中的右边节点，然后再父结点中递归删除右节点的索引。
并发B+树的实现方法，并发怎么做，B+树乐观锁怎么实现？
节点内部的数据的安全性，不能让多线程同时修改。
节点的安全性，保护节点间分裂合并操作。
所以我们需要锁来保护B+树的并发安全，并提高并发度。latch crabing是B+树常用的并发策略，意思是锁的释放和获取就像螃蟹一样在节点间爬行。
对根节点加锁：根节点是特殊的，因为它没有父节点的保护。你需要一个独立的锁来保护根节点，在任何对根节点的操作开始前获取这个锁，操作完成后释放锁。
为兄弟节点加锁：在进行节点借用（borrow）或合并（merge）时，需要先对相关的兄弟节点加写锁，即使它们的父节点已经被锁定。这是为了防止在操作过程中由于其他线程的介入导致的数据不一致。
死锁的考虑：正确的加锁顺序和策略可以避免死锁。例如，在同一个父节点下的子节点间，不会同时进行会导致不安全的删除操作，因此按照一定的顺序加锁可以避免死锁。
修改子节点的父指针不加锁：在节点借用或合并后，修改子节点的父节点指针时不需要再次加写锁，因为这可能会导致死锁。更改父指针通常是安全的，因为它不会影响到其他正在进行的插入或删除操作。
优化的提前解锁场景：在某些情况下，比如节点重分布（不影响父节点大小）时，可以提前释放父节点及其祖先的锁以提高并发度。
避免在向上递归过程中给父节点加锁：如果父节点已经在PageSet中被锁定，向上递归时就不需要再次加锁。
数据库宕机了，要怎么恢复，有一些内容在内存中还没有写入到硬盘要怎么办
检查数据库服务器的日志文件，重启数据库服务前，建议检查数据库文件的完整性。某些数据库系统提供了工具来检查和修复数据库文件（例如，MySQL的myisamchk工具）。
如果数据库系统使用事务日志（如WAL日志），在发生宕机时，尚未持久化到硬盘的数据可能还可以从这些日志中恢复。
如果上述步骤不能恢复所有数据，你可能需要从最近的备份中恢复数据。根据备份和恢复策略，这可能是全备份、增量备份或差异备份。
对于某些数据库（如MySQL），如果你有二进制日志（binlog）的备份，可以使用这些日志恢复到宕机时刻的状态。这要求你之前已经开启了二进制日志记录。
怎么进行死锁检测，实现难度在哪里

增删改查打日志¶

这里的“增删改查”指的是数据库操作中的增加（INSERT）、删除（DELETE）、修改（UPDATE）和查询（SELECT）。而“打日志”则是指在执行这些操作时，系统会记录日志，包括操作的具体内容、执行时间、涉及的数据等，这些信息对于事后分析死锁发生的原因非常有用。

Core Dump下来之后看栈：只有gdb看coredump能用用了¶

Core Dump：当程序异常终止（如遇到死锁时可能发生的系统挂起或崩溃）时，操作系统可以生成一个core dump文件，该文件包含了程序终止时的内存镜像，包括程序计数器、寄存器内容、内存中的数据等。
看栈：指的是分析core dump文件中的调用栈（或堆栈）信息。调用栈是一种记录程序中函数调用序列的数据结构，通过分析它，开发者可以确定程序崩溃时的状态，包括哪些函数被调用、在哪里调用等。这对于定位死锁发生的原因和上下文非常有帮助。
具体的结构体实现是怎么样的？
B+树的非叶子节点结构体¶

B+树的非叶子节点主要用于指导搜索路径，其结构体通常包含：

键数组：存储用于搜索的键值。这些键将数据范围划分为不同的段，每个段指向一个子节点。
子节点指针数组：每个键对应一个指向子节点的指针。如果非叶子节点有n个键，则会有n+1个子节点指针，因为要涵盖所有可能的数据范围。
键的数量：表示当前节点存储的键的数量。
可选的父节点指针：有些实现中可能包含指向父节点的指针，以便于从叶子节点向上遍历。

struct BPlusTreeInternalNode {
    int keyCount; // 存储的键的数量
    int keys[MAX_KEYS]; // 键数组
    BPlusTreeNode* children[MAX_CHILDREN]; // 子节点指针数组
    // 可选：BPlusTreeNode* parent; // 父节点指针
};

### B+树的叶子节点结构体

B+树的叶子节点包含实际的数据指针或数据值，其结构体通常包含：

键数组：与非叶子节点相同，存储键值，这些键值对应实际的数据。
数据指针数组：每个键对应一个数据指针，指向实际的数据记录。
键的数量：表示当前节点存储的键的数量。
一个指向下一个叶子节点的指针：用于叶子节点的链表连接，以便于顺序访问。
可选的父节点指针：有些实现中可能包含指向父节点的指针。

struct BPlusTreeLeafNode {
    int keyCount; // 存储的键的数量
    int keys[MAX_KEYS]; // 键数组
    void* dataPointers[MAX_KEYS]; // 数据指针数组
    BPlusTreeLeafNode* next; // 指向下一个叶子节点的指针
    // 可选：BPlusTreeNode* parent; // 父节点指针
};

需要注意的是，MAX_KEYS和MAX_CHILDREN的具体值取决于B+树的阶数，而这个阶数通常是基于磁盘块的大小来决定的，以优化磁盘I/O操作。

如何验证B+树索引写对了呢？

15445问题¶

buffer pool¶

B+树¶

增删改查打日志¶

Core Dump下来之后看栈：只有gdb看coredump能用用了¶

B+树的非叶子节点结构体¶