# cmu15445 **Repository Path**: qiao-peng-cheng/cmu15445 ## Basic Information - **Project Name**: cmu15445 - **Description**: QPC的bustub面向磁盘的关系型数据库管理系统 - **Primary Language**: Unknown - **License**: MIT - **Default Branch**: 2023spring - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2023-09-24 - **Last Updated**: 2024-09-15 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README 关于课程 CMU15445 2023spring是卡耐基梅隆大学的一门数据库内核入门课，配套有homework和5个project,基于一个名为bustub的面向磁盘的数据库内核，通过project1~project4四个实验，来实现缓冲池管理，B+树索引，查询执行，事务管理，每个实验的代码量在1000行左右，且全部使用modern cpp编写，写完了所有的实验并且顺利通过gradescope的测试之后，可以建立一个比较清晰的数据库内核的体系架构，并且提升自己的工程能力。 课程资料 课程网站:https://15445.courses.cs.cmu.edu/spring2023/ 测试网站:https://www.gradescope.com/ B站Moody老师的课程讲解:https://www.bilibili.com/video/BV1bQ4y1Y7iT/?spm_id_from=333.337.search-card.all.click 还有一些大佬的博客: 22fall: xiao:https://zhuanlan.zhihu.com/p/592547524 十一:https://www.zhihu.com/people/shi-yi-12-95-43 23spring: 码呆茶：https://www.zhihu.com/people/Dlee-01 关于实验 project0： 实现可持久化字典树。因为此课程使用modern cpp编写，所以要先有一定的modern cpp的基础，才能够顺利的完成此课程，project0并不涉及任何的数据库知识，有modern cpp编程基础的同学可以跳过。主要涉及的modern cpp的语法有 std::move移动语义，左右值引用，智能指针等。 project1: 实现数据库内核的缓冲池管理，位于整个内核的最底层，将disk中的页page拿出放到缓冲池中进行管理，通过缓冲池的管理实现页page与上层交互。主要实现的方法有NewPage新建page,DeletePage删除page,以及刷脏等操作。 通过LRU-K页面置换算法来实现page的驱逐，并且通过加锁实现并发控制。最后引入基于PageGuard的RAII机制，来帮助我们管理页。 project2: 为了支持快速数据检索，实现并发B+树索引。对下层的Buffer pool中的page做索引，以支持SQL层执行查询计划时的快速数据查找。自己从0实现B+树的插入，删除，查询等操作，之后要在B+树的叶子节点层实现迭代器，以支持B+树叶子节点的顺序查询。在并发B+树的实现中，使用蟹行协议来实现锁的管理，并且有悲观锁和乐观锁两种加锁方式。 project3: 基于火山模型，实现SQL层的执行器，并且书写几个优化规则。自己实现seq_scan,index_scan,insert,delete,join, agg,join,sort,limit等算子，并且实现join,limit的优化计划。整体上难度不大，但是从project3开始，就可以将project1实现的缓冲池管理器，project2实现的B+树索引利用起来，跑一个单机的数据库了，并且可以执行一些SQL语句。 project4: 实现并发事务管理。实现事务的并发执行。整体上，通过2PL的事务并发控制，来保证事务并发执行时的隔离性。支持Read Uncommitted, Read Committed, Repeatable Read三种隔离级别，通过共享锁，独占锁，意向共享锁，意向独占锁，共享意向独占锁配合使用，来实现这三种隔离级别。事务运行时，向锁管理器请求对应的锁。并且实现一个后台死锁检测线程，来及时检测死锁，并且abort相关事务。 实验难度 个人认为，p2≈p4>>p3≥p1. 总结 在暑假完成了xv6操作系统的学习之后，就对这种自己阅读课程handout,自己查找相关blog,自己编程，并且通过线上测评的学习方式大为赞叹，深切体会到这种方式对于自己大有裨益。 在学习这门课程之前，自己并没有接触过任何数据库有关知识，甚至没有学习过SQL语句，更不用说深入内核了。 但是在学习过程中，自己一边看对应的帆船书，一遍看B站Moody老师的讲解，同时查找相应的博客，一点点跟下来，终于在两个月左右的时间将所有的实验都通过了。整体上，基本上每天都在写，每天花费时间大概在4~5小时左右，我觉得要是有数据库的基础，应该会更快一点。 目前在备考期末，所以没时间来写详细的讲解文章，计划在一月份考完试之后将对应的文章发布出来。（其实已经详细的写完了笔记，删删改改就可以发出来了） p0~p4的讲解。 p3中涉及到的Bustub SQL层 p4中涉及到的事务管理。