Posts

Overview 这个实验应该是最难的一个实验了。。。（感觉和Project 4 —— Transaction实现的难度差不多） 另外，2022fall版本的B+ tree更是变态，因为几乎没有给任何内部的API，让人无从下手。建议到 Github repo 里找到20年的，我基本是根据里面定义的函数来实现的。 实验材料贴心的为你分成了两个检查点，四个小任务。 Checkpoint #1 Task #1 - B+Tree Pages Task #2 - B+Tree Data Structure (Insertion, Deletion, Point Search) Checkpoint #2 Task #3 - Index Iterator Task #4 - Concurrent Index Task #1 - B+Tree Pages 第一个任务算是热身，主要是搞清楚 B+ 树的一些类之间的关系。 我们知道，数据库中的索引也是数据，同样以 page 的形式被组织。我们先来看看要完成的这些类之间的关系。 B+ tree internal page 与 B + tree leaf page 都继承自B + tree page，B + tree page 中定义了 B+ 树每个结点的一些信息。而B + Tree 这个类则是Checkpoint 1的主要对象，它对internal page 以及 leaf page 进行管理，并对外开放接口。而在内存中，internal page 与 leaf page 都属于 page 的一部分，关系如下图所示。他们就是 page 中的 data 部分。因此，每次 从 buffer pool manager 得到一个 page 后，若是将他们用作 B+树的结点，则需要对这个 data 进行释义，也就是将他强制转化为internal page 或者 leaf page。这在 C++ 中通过 reinterpret_cast 完成。 ...

Buffer Pool Manager cmu15445 是一门关于数据库管理系统（DBMS）设计与实现的经典公开课，是很多dba和内核开发人员的入门课程。开课教授Andy Pavlo 非常风趣幽默，他有自己上课的DJ，他曾在浴缸里录课，且时常语出惊人。这门课的实验项目BusTub非常有挑战性，并对所有人开放评测资源。 Overview BusTub是一个面向磁盘的 DBMS(Database Management System)。由于磁盘上的数据不支持字节粒度的访问，这就需要一个管理页的中间层，而 Andy 坚持“The OS is not your friend”， 反对使用 mmap 进行页操作，因此实验一的目标便在于通过实现 Buffer Pool Manager 主动管理磁盘中的页（page）在内存中的缓存，从而，最小化磁盘访问次数（时间上）、最大化相关数据连续（空间上）。 这次实验有三个子任务，分别是 Task #1: Extendible Hash Table Task #2: LRU-K Replacer Task #3: Buffer Pool Manager Instance 可拓展哈希表是这个是实验中相对独立的模块。这里不会讲它的细节，后面的两个任务中需要用到哈希表的地方我直接用std::unordered_map替代，而且效率还更高。应该是因为 Extendible Hash Table 要求线程安全，为了方便在我在每个函数入口都加了大锁。 想要 Extendible Hash Table 具体细节的可以看这个b站视频。关于它的优化，我想可以进行更细粒度的锁管理甚至写一个无锁(lockfree)的哈希表。 Buffer Pool Manager 在后两个实验开始之前，我建议先将Task #2和Task #3的实验材料完整的看完在开始写代码。因为 replacer 和 buffer pool manager 有较大程度的耦合。很多API设计需要对照两个组件才能知道自己应该维护的数据与功能的边界。为了更符合直觉，我会先阐述 buffer pool manager 的设计，同时会穿插着 LRU-k 的API什么时候，在哪用。 ...

vscode 插件： C/C++, ~ Extension Pack, Themes, InteliCode CMake Tools, CodeLLDB Vim remote ssh, docker Error Lens, GitLens user的settings.json "editor.fontFamily": "Fira Code", "workbench.panel.defaultLocation": "right", "vim.handleKeys": { "<C-c>": false, "<C-f>": false, "<C-x>": false, "<C-a>": false, "<C-p>": false, }, "C_Cpp.vcFormat.newLine.beforeOpenBrace.block": "sameLine", "C_Cpp.vcFormat.newLine.beforeOpenBrace.function": "sameLine", "editor.formatOnSave": true, "C_Cpp.clang_format_fallbackStyle": "{ BasedOnStyle: LLVM, UseTab: Never, IndentWidth: 2, TabWidth: 2}", pip, python, pyenv 使用pyenv控制多个python版本 pyenv versions # 查看所有安装的python脚本 pyenv install 3.8.0 # 安装python 3.8.0 pyenv global 3.8.0 # 将3.8.0设置为全局python，对应pip也会改变 删除__pycache__ find . -name "*.pyc" -type f -print -exec rm -rf {} \; about clash # start.sh nohup ./clash -d . >/dev/null 2>&1 & #shutdown.sh ps -A | grep clash | awk '{print $1}' | xargs kill 暂时设置7890做全局代理 ...

Computer Network introduction dominant model : bidirectional, reliable byte stream connection http: hypertext transfer protocol : designed to be a document centric way for programs to communicate. Client —> Server model Bit-Torrent: (peer-to-peer model) a client requests document from other clients, a single client can request from many others. these collections of collaborating clients are called swarms when a client wants to downloads a file, it first find torrent, usually using www and download using http. torrent file describes information about data file, also tells bit-torrent about the tracker (a node keeps track names of clients of the swarm) ...

icpc模板 Previous Next     / [pdf] View the PDF file here. algorithm-template Competitive Programming template ...