分类: Database

5 篇文章

Bitmap Indexing(位图索引)
Bitmap Indexing 顾名思义,使用位图实现索引。广泛应用于大规模数据查询,OLTP 数据库。 为证明位图索引的优势,下面假设了一张数据表 employee。ID 为员工 ID,自增主键,唯一。Job 只含有 A,B 和 C 三种类型。Sex 则只有男和女两种类型。 IDJobSex1A女2B男3A男4C女 因我们需要频繁的对 emplo…
2021 CMU 15-445 实验笔记
陆陆续续终于把 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 算法实现
Extendible Hash Table 属于动态哈希的一种,网上有很多关于它的介绍,但是真的在实现它的时候,或多或少有着很多问题。网上很多教程光讲怎么扩容,不讲收缩,而且网上很多都是概念性的东西,不讲代码实操。因 CMU 15-445 的课程需要,自己捣鼓了一下算法流程,这里分享一下。 在看之前请自行了解 Extendible Hash Tab…