CMU 15-445 Database Systems Project2
Project #2 - B+Tree Task #1 - B+Tree Pages 这一部分没什么好说的,把他给的函数写出来就行,基本都是一两行的事 Task #2 - B+Tree Data Structure (Insertion, Deletion, Point Search) 逆天 Task 之一 B+Tree 这东西看着原理简单,在内存池上写起来怪恶心的 比较简单的是查找,直接顺着往下定位到叶子节点就行。关于每个节点上的定位可以直接遍历或者二分定位。我用的二分,不过估计效率差别不大,瓶颈不应该在这一块 至于插入,最好先画个图仔细想清楚再写,不然就会向我一样改了好几版,10 天才摸出来这个 Task,感觉 DSA 白学了( 我在向上更新的时候用的递归,感觉比较好理解。需要注意 Split 时也要更新子节点的 parent_page_id 然后是删除。因为课件讲得不是很细致,有些细节也稍微卡了一会。在 Merge 时需要给右边节点的第一个子节点增加一个对应的 Key,这个 Key 可以直接取父节点对应的...
[Algorithm] Bloom Filter 布隆过滤器 / Cuckoo Filter 布谷鸟过滤器
背景故事什么的没有。 Bloom Filter 布隆过滤器 用于判断集合中是否存在某个值,但有可能误判(将不存在判断为存在) 原理类似 Hash Table,开一个大小为 nnn 的 bitset,设计 kkk 个 Hash 函数,插入元素时将 bitset 中 Hash 值对应的位设为 111。查询时若 kkk 个位置均为 111 则认为存在。 优点:内存占用小,时间复杂度稳定 O(k)O(k)O(k) 缺点:不能删除(如果需要删除可以将 bitset 改为普通计数数组,但这样内存优势就不大了),存在误判 Bloom Filter Arguments Analysis 考虑插入 mmm 个元素后,某个位置为 111 的概率为 p1=1−p0=1−(1−1n)mk≈1−e−mknp_1 = 1 - p_0 = 1 - (1 - \frac1n)^{mk} \approx 1 - e^{-\frac{mk}{n}} p1=1−p0=1−(1−n1)mk≈1−e−nmk 其中用到 limn→+∞(1−1n)−n=e\lim\limits_{n\rightarrow...
CMU 15-445 Database Systems Project #1 - Buffer Pool
Project #1 - Buffer Pool Project 目标:实现一个线程安全的 buffer pool,用于在硬盘和内存之间移动数据 Task 分为三部分: Extendible Hash Table LRU-K Replacement Policy Buffer Pool Manager Instance 可以使用 C++17 的一些容器辅助(但注意 STL 容器不是线程安全的) Task #1 - Extendible Hash Table 实现一个可以自动扩张的线程安全 Hash Table 这里的 Extendible Hashing 指的是课件中的算法,不是单纯的可扩张,一开始看代码还没看懂 感觉课件上不是特别清楚,附一篇知乎文章 话说阅读框架好痛苦,经常对不上电波( 首先是 Bucket 的实现,没什么难点 因为 Bucket 只供 ExtendibleHashTable 调用,不需要考虑多线程问题 clang-tidy 经常提示用 STL...
CMU 15-445 Database Systems Homework #1 - SQL
Homework #1 - SQL 对 Lecture #02: Advanced SQL 的一个简单测试,使用 SQLite 练习 SQL 语句。 Ubuntu 安装 SQLite:sudo apt-get install sqlite3 根据 Homework 界面下载数据集并进行配置,需要用到的 relations 结构如下: Q1 一个例子,没有分数,直接给了答案 但恕我没有看懂这 Details 和 Answer 怎么完全对不上 不影响,直接交就完事了 1234SELECT DISTINCT(language)FROM akasORDER BY languageLIMIT 10; Q2 12345SELECT primary_title, premiered, runtime_minutes || ' (mins)'FROM titlesWHERE genres LIKE '%Sci-Fi%'ORDER BY runtime_minutes DESCLIMIT 10; 话说既然 Gradescope...
CMU 15-445 Database Systems Project #0 - C++ Primer
在线测试需要使用 Gradescope,使用课程提供的课程码 PXWVR5,学校填 Carnegie Mellon University,Student ID 不需要。 Project #0 - C++ Primer 既然这门课用的 C++,那么就需要考察学生的 C++ 水平。CMU 15-445 的要求:C++17, GDB。 鉴于课程使用的工具,最好在 Linux 下做此课程实验。 首先需要 clone 一份 CMU 的 bustub(需要去 Release 手动下载 Fall2022 版本,或者手动 reset 到对应的 commit d830931a9b2aca66c0589de67b5d7a5fd2c87a79,否则内容对应不上)。 Task #1 - Templated Trie 在原有模板上实现一颗 Trie 树。 没什么好说的,只要知道 Trie 树是个什么东西就行了,直接模拟,总共就几十行代码。 在写的时候可能遇到的主要问题:不会用智能指针等现代 C++ 内容,只能边查边写,多用用就会了。 (不过我一直感觉 C++ 的智能指针用着怪难受的,Rust...
CMU 15-445 Database Systems Notes
CMU 15-445 DBS Fall2022 开新坑.jpg 抄了抄之后感觉不如直接看提供的 Notes( 就当是强迫自己看课件用的 Lecture #01: Course Overview & Relational Model 通用数据管理系统(DBMS, Database Management System):支持定义、创建、查询、更新、管理。 Data model:数据模型,描述数据的概念的集合 Schema:模式,指定数据模型下对一类特定数据的描述 本课程重点:关系模型(Relational Model) 将数据存放在简单结构中(relations) 通过高级语言访问数据,由 DBMS 决定最佳方案 存储方式由 DBMS 实现 Relation:一个无序集合,可以看成一个 nnn 列的表(n-ary relation),每一列对应一种属性(attributes / keys) Tuple:一个 nnn 元组,relation 中的每一行就是一个 tuple Primary key:主键,在 relation 中可以唯一确定一个...
[C++] 构建工具 Bazel 简单使用笔记
Bazel 是由 Google 开源的一款构建工具,支持 C++ 等多种语言 我个人是不喜欢 CMake 或者 GNU Make 的,感觉语法太丑了(?) 最近看了几个项目用的都是 Bazel,看起来语法似乎还行?对我 xp 于是打算简单学一下,记录一点常见用法以后好抄 安装 对 Windows 系统,直接按照官网方法下载即可,也可以去 Github 上下载二进制文件自己配置环境变量。 如果在 VSCode 中使用了 Bazel 插件,似乎还要另外下载 buildtools 文件结构 想要使用 Bazel,只需在项目的根目录下新建一个 WORKSPACE 文件即可。 在项目中在不同地方会有一个或多个 BUILD 文件,用于表示项目的不同模块。 一个例子: 12345> project > src - main.cpp - BUILD - WORKSPACE 然后在 BUILD 文件中写上相应的配置: 1234cc_binary( name = "main", srcs =...
简单探索:扫雷的地图生成与求解算法
前言 之前在 b 站上刷到了影视飓风的 “扫雷,但是是真人3D版!” 这个视频,总之很有感觉! 开始想着能不能直接用 UE5 复现一个,不过自己也没有那个能力,但是对扫雷的地图生成算法产生了一些兴趣。高中的时候经常和同学在 seewo 上面多开扫雷,当扫雷地图大了之后总遇到需要猜的死局,虽然后来在网上找到了一个可以生成绝对有解地图的扫雷,不过当时并没有想明白原理,正好这次尝试一下。 扫雷基本定义与规则 游戏初始局面为一块 n×mn\times mn×m 的矩阵,每一格都是未知的,玩家可以点击打开格子,若格子下是雷则游戏结束(一般保证第一次点击不是雷),否则格子下会出现一个数字,代表此格周围 888 格中的地雷数。若周围没有雷则会递归打开周围的 888 个格子。 而因为机制问题,有时候会出现因为条件不够需要猜测的局面。针对此衍生出了几种不同的玩法,详见下图(Source): 部分玩法的在线试玩: Kaboom Simon Tatham’s Mines 扫雷问题求解 先来看看如何对指定的局面进行求解。 首先需要明确的是,扫雷的求解是一个 NP-Complete...
[C++] 多线程 / 异步编程 简易笔记
前言 在 C++ 11 之前,C++ 标准库并没有提供内置的多线程支持,实现多线程编程通常需要引入外部第三方库,Linux 上常用 pthread.h(POSIX Threads),而 Windows 上则需要调用 Windows API,可以使用 pthreads-win32 库或 Boost.Thread 库来实现,跨平台非常麻烦。在 C++ 11 中引入了官方的多线程库 <thread>,大大方便了代码的编写。 不过如果在 Windows 上使用 MinGW-GCC 的话,若根据网上的旧教程使用 MinGW 8.1.0 版本的话需要注意安装时选择 Posix 而非 Win32,否则 <thread> 不完整,推荐去 Github 下载最新版。 std::thread 在 C++ 11 中使用 std::thread 创建线程,头文件...
概率论 复习笔记
其实都是照着抄的 Chapter 1 样本空间与概率 1.3 条件模型 条件概率:P(A∣B)=P(A∩B)P(B)P(A|B)=\frac{P(A\cap B)}{P(B)}P(A∣B)=P(B)P(A∩B) 乘法定律:P(AB...)=P(A)P(B∣A)...P(AB...)=P(A)P(B|A)...P(AB...)=P(A)P(B∣A)... 1.4 全概率定理与贝叶斯准则 A1...AnA_1...A_nA1...An 为样本空间的一个分割,则: 全概率定理:P(B)=∑iP(Ai∩B)=∑iP(Ai)P(B∣Ai)P(B)=\sum_i P(A_i\cap B)=\sum_i...