Hash Table Latching

Duplicate Keys

• Append Record Id
  • 将tuple的record id作为key的一部分，从而保证每个键都是不同的

B+ Tree

B+树是一个自平衡的树结构，查找，插入，删除都是O(log n)，B+是是一个M-way的搜索树

参考 https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/

TASK1

实现HashTableDirectoryPage和HashTableBucketPage两个类

Index

Hash Table

Hash Function

• CRC-64
• MurmurHash
• Google CityHash
• Facebook XXHash
  • 一般用这个
• Google FarmHash

Static Hasing Schemes

Linear Probe Hasing

就是线性探测法

LRU REPLACEMENT POLICY

这个task是做lru替换类，负责跟踪buffer pool中的page

Buffer Pool Organization

Buffer Pool在内存中是以一个固定大小数组的形式来呈现的，数组中每个元素都有固定的大小，称为frame
当DBMS需要一个page的时候，DBMS可以让硬盘中的page转存到Buffer Pool中来

占用空间大的值在tuple中的存储形式

Overflow storage pages

如果c是较大的值的话，c的位置可以放置指针，指向一个格外的页存储真实的数据，如果数据过大，可以在一个overflow page中再指向下一个overflow page。overflow page是在内存中常驻的，并且overflow page对于用户层面是透明的。

DISK-ORIENTED DBMS

数据库在内存中设立了buffer pool来缓存外存中的信息