Bitmap Indexing 顾名思义，使用位图实现索引。广泛应用于大规模数据查询，OLAP 数据库。 为证明位图索引的优势，下面假设了一张数据表 employee。ID 为员工 ID，自增主键，唯一。Job 只含有 A，B 和 C 三种类型。Sex 则只有男和女两种类型。 IDJobSex1A女2B男3A男4C女 因我们需要频繁的对 emplo…

陆陆续续终于把 CMU 15-445 刷完了（中间插了个 TinyKV），这也算是自己数据库的启蒙之课。编码耗时共计 98 小时 43 分钟。 我个人给整个项目难度评级：Project 1 < Project 4 < Project 3 << Project 2。其中 Project 2 难度最大，主要没啥参考资料，今年的是…

数据库的事务 transaction （txn）很有搞头，特此特别记下这篇笔记，方便自己的回顾，如有错误，请指正。 Transaction 数据库事务以 Begin() 开始，以 Commit() 或 Abort() 结束。事务需要满足 ACID。 ACID Atomicity A：Atomicity 原子性，即多个操作合并在一起，如一个原子一样不…

这一篇文章主要参照 CMU 15-445 Project 3 的 Query Execution 章节，特此记录。 本文所有的 Cost 均为 IO Cost。 数据库操作主要包含如下三大类： Access：Sequential ScanModifications： Insert, Update, DeleteMiscellaneous：Neste…

Extendible Hash Table 属于动态哈希的一种，网上有很多关于它的介绍，但是真的在实现它的时候，或多或少有着很多问题。网上很多教程光讲怎么扩容，不讲收缩，而且网上很多都是概念性的东西，不讲代码实操。因 CMU 15-445 的课程需要，自己捣鼓了一下算法流程，这里分享一下。 在看之前请自行了解 Extendible Hash Tab…