禅茶一味

明天再说的自留地

0%

发表于 分类于 Valine：
本文字数： 5.9k 阅读时长 ≈ 5 分钟

知识点：浮点数，整数，逻辑运算，信息存储，补码

CSAPP的第一个lab, 难度不大，代码如下。

阅读全文 »

发表于 更新于 分类于 Valine：
本文字数： 13k 阅读时长 ≈ 12 分钟

TASK #2.B - B+TREE DATA STRUCTURE (DELETION)

您的B+树索引需要支持删除。如果删除导致某些页面低于占用阈值，您的B+树索引应该正确地执行合并或重新分发。同样，你的B+树索引只能支持唯一键，你应该遵循TASK #2.A中的相同指导方针。

Remove函数

  • 先判断树是否为空。
  • 调用FindLeafPageByOperation函数找到待删除的节点（已上写锁）。
  • 在leaf中删除key（如果不存在该key，则size不变）。
  • 如果删除失败，解锁并unpin自己以及经过的所有节点。
  • 如果删除成功，调用CoalesceOrRedistribute函数，进行合并或重分配（或不做处理）。
  • 还需判断叶子节点是否需要删除。
阅读全文 »

发表于 更新于 分类于 Valine：
本文字数： 15k 阅读时长 ≈ 14 分钟
实现b_plus_tree.cpp/InsertIntoLeaf函数所涉及到的相关函数。

您的B +树索引只能支持唯一键。 也就是说，当您尝试将具有重复键的键值对插入索引时，它应该返回false

对于checkpoint1，仅需要B + Tree索引支持插入（Insert）和点搜索（GetValue）。 您不需要实现删除操作。 插入后如果当前键/值对的数量等于max_size，则应该正确执行分割。 由于任何写操作都可能导致B + Tree索引中的root_page_id发生更改，因此您有责任更新（src / include / storage / page / header_page.h）中的root_page_id，以确保索引在磁盘上具有持久性 。 在BPlusTree类中，我们已经为您实现了一个名为UpdateRootPageId的函数。 您需要做的就是在B + Tree索引的root_page_id更改时调用此函数。

您的B + Tree实现必须隐藏key/value等的详细信息，建议使用如下结构：

阅读全文 »

发表于 更新于 分类于 Valine：
本文字数： 6k 阅读时长 ≈ 5 分钟

B+TREE LEAF PAGE

Leaf Page存储一个有序的m键条目和m值条目。在你的实现中，值应该仅为64位的record_id，用于定位实际元组存储的位置，参见在src/include/common/RID.h下定义的RID类。叶子页与内部页在键/值对的数量上有相同的限制，并且应该遵循相同的合并、重分发和拆分操作。

必须在指定文件中实现内页。只允许修改头文件(src/include/storage/page/b_plus_tree_leaf_page.h)及其对应的源文件。

要点:即使叶子页和内部页包含相同类型的键，它们也可能有不同类型的值，因此叶子页和内部页的max_size可能不同。

阅读全文 »

发表于 更新于 分类于 Valine：
本文字数： 9.5k 阅读时长 ≈ 9 分钟

Task1 - B+TREE PAGES

您需要实现三个页面类来存储B+树的数据。

  • B+Tree Parent Page
  • B+Tree Internal Page
  • B+Tree Leaf Page
阅读全文 »

发表于 更新于 分类于 Valine：
本文字数： 11k 阅读时长 ≈ 10 分钟

Task1 LRU REPLACEMENT POLICY

任务描述

这个任务要求我们实现在课堂上所描述的LRU算法。

你需要实现下面这些函数。请确保他们都是线程安全的。

  • Victim(T*) : Remove the object that was accessed the least recently compared to all the elements being tracked by the Replacer, store its contents in the output parameter and return True. If the Replacer is empty return False.

  • Pin(T) :This method should be called after a page is pinned to a frame in the BufferPoolManager. It should remove the frame containing the pinned page from the LRUReplacer.

  • Unpin(T) : This method should be called when the pin_count of a page becomes 0. This method should add the frame containing the unpinned page to the LRUReplacer.

  • Size() : This method returns the number of frames that are currently in the LRUReplacer.

阅读全文 »