CMU14-445 Lab
Lab1.Buffer Pool
这是CMU数据库系列的第一个实验,第一个实验需要我们完成关于Buffer的一些功能.在完善Buffer的功能之前,我们先了解一下buffer的一些基本知识.
buffer在这里面和操作系统很像,是主存和辅存的缓冲地带,我们需要完成的是两个特别重要的数据结构,一个是Disk Manager,用我的话说就是页表,一个是LRU Replacer,这个数据结构研究,在缓冲地带满的时候我们应该替换谁进入到辅存.这两个数据结构所存储的信息单位量是一样的(也就是说这两个数据结构都存储了n个块[你也可以认为是“页”]的信息).两个数据结构通过Pin和Unpin来互相作用.
实验1.1 LRU REPLACEMENT
实验提示:修改src/include/buffer/lru_replacer.h和src/buffer/lru_replacer.cpp.
首先我们知道LRU Replacer是一个依赖LRU算法进行替换的一个结构体,我们在操作系统和组成原理的课程中已经知道,模拟LRU算法一般使用堆栈,我们现在使用堆栈来进行模拟:
首先在头文件中添加有关堆栈的一些信息;
size_t capacity; //容量 size_t size; //当前大小 std::list<frame_id_t> lists; //存储帧的栈,用list实现 std::unordered_map<frame_id_t , int> maps; //哈希映射,映射帧和是否在LRU Replacer里面. std::mutex locks;
定义了这么多成员,我们可以实现类的方法了:
1、构造函数.(略)
LRUReplacer::LRUReplacer(size_t num_pages) { capacity = num_pages; maps.clear(); lists.clear(); size = lists.size(); }
2、Victim函数:
这个函数选择一个帧来被替换.返回值是是否成功输出.具体的做法是从栈中选择栈顶返回即可.然后在maps中删除掉这个帧即可.
bool LRUReplacer::Victim(frame_id_t *frame_id) { if(lists.empty()) return false; locks.lock(); frame_id_t lasts = lists.back(); maps.erase(lasts); lists.pop_back(); *frame_id = lasts; locks.unlock(); return true; }
3、Pin函数
Pin的意思就是固定,这个意思就是Disk Manager固定了某一个页,希望这个页不会被LRU Replacer选中然后被替换掉.那么首先调用maps,看看LRU Replacer中是否存在这个帧,存在的话就删除,不存在的话就不作任何处理.
void LRUReplacer::Pin(frame_id_t frame_id) { if(maps.count(frame_id) == 0) return; locks.lock(); lists.remove(frame_id); maps.erase(frame_id); locks.unlock(); }
4、UnPin函数
UnPin函数的意思是解除固定,这个意思就是Disk Manager解除固定某一个页,表示Disk Manager最近不需要使用这个页了,LRU Replacer最近可以对其进行替换操作.首先第一步就是查看这个帧是否存在于LRU Replacer中.如果没有就需要放进LRU Replacer中,那么就会存在问题,问题就是,万一我LRU Replacer满了怎么办?满了的话就可以选择一个元素替换下去,然后在插入.(跟我们在操作系统课程上面学习的一样,从栈顶取一个元素,然后把它放入栈底)
void LRUReplacer::Unpin(frame_id_t frame_id) { if(maps.count(frame_id) != 0) return; locks.lock(); //如果已经满了,则需要淘汰一个然后放入 LRUReplacer 中 if (lists.size() == capacity) { frame_id_t last_frame = lists.back(); maps.erase(last_frame); lists.pop_back(); } lists.push_front(frame_id); maps[frame_id] = 1; locks.unlock(); }

先看实验的最后怎么make的吧,一开始太智障直接cd进目录调gcc,这下丑大了,重写了一份…
实验1.2 BUFFER POOL MANAGER INSTANCE
提示:修改src/include/buffer/buffer_pool_manager_instance.h和src/buffer/buffer_pool_manager_instance.cpp
首先我们先来了解一下BUFFER POOL的一些成员(这个实验不需要我们添加成员),一个是存储每个页的指针的指针数组,在后面我们会使用这个结构来给定页的id获得一个页的指针,接着就是页表成员,将物理帧和页的id进行对应,接着就是空闲物理帧以及之前做的替换器元素.(其实页和物理帧是相互统一的概念,物理帧是一个物理概念,代表了一块空闲的内存空间,页就是记录数据的单位,当物理帧被赋值,被填入数据的时候,它就变成了一个页.**当然,页表的id某种程度上反映了辅存的位置**)
/** Array of buffer pool pages. */ Page *pages_; /** Pointer to the disk manager. */ DiskManager *disk_manager_ __attribute__((__unused__)); /** Pointer to the log manager. */ LogManager *log_manager_ __attribute__((__unused__)); /** Page table for keeping track of buffer pool pages. */ std::unordered_map<page_id_t, frame_id_t> page_table_; /** Replacer to find unpinned pages for replacement. */ Replacer *replacer_; /** List of free pages. */ std::list<frame_id_t> free_list_; /** This latch protects shared data structures. We recommend updating this comment to describe what it protects. */ std::mutex latch_;
1、NewPgImp函数
这个函数主要让我们申请一个新的Page,然后把Page的ID放入到page_id中,然后返回这个Page的指针.关于这个函数,提示已经说明地很明显了:
首先第一步,遍历一遍pool_size_,看看是不是所有的Page都被Pin了,如果是,那么就返回空指针,代表找不到可以申请的页.
第二步就是从freelist中获取一个新的帧,如果freelist为空,就代表我们不得不得替换一个页下来,这个页可以调用Replacer的Victim函数获得.如果要替换的页是脏的,我们要把这个页写进磁盘中.(脏块,参考组成原理)
第三步就是从给这个页一些初始数据,比如说引用数为1,页的id是page_id,存储的内容为空,最后Pin一下这个页,返回即可.然后把这个页填入到物理帧中然后加入到页表中.
代码略
2、FetchPgImp函数
这个函数主要根据页面的id来获取一个页的指针,这个提示说明的也很明显了
首先第一步,在页表中寻找page_id,看这个页是否真正存在,如果存在就跳过,如果不存在,按照第一个函数的方式申请一个页,然后把页号加载一下,把辅存的内容加载到p->data_里面,Pin一下即可.
代码如下:
Page *BufferPoolManagerInstance::FetchPgImp(page_id_t page_id) { // 1. Search the page table for the requested page (P). // 1.1 If P exists, pin it and return it immediately. // 1.2 If P does not exist, find a replacement page (R) from either the free list or the replacer. // Note that pages are always found from the free list first. // 2. If R is dirty, write it back to the disk. // 3. Delete R from the page table and insert P. // 4. Update P's metadata, read in the page content from disk, and then return a pointer to P. frame_id_t fid; Page* p = nullptr; // step 1.1. if(page_table_.find(page_id) != page_table_.end()){ fid = page_table_[page_id]; pages_[fid].pin_count_++; // pin it. replacer_->Pin(fid); return &pages_[fid]; } latch_.lock(); // step 1.2. if (free_list_.empty()) { // pick from free list first. //can't find a page that can be flushed. if (!replacer_->Victim(&fid)) { return nullptr; } else { // the page placed in the lrureplacer need to be flushed. // send it to the disk p = &pages_[fid]; if (p->is_dirty_) { disk_manager_->WritePage(p->page_id_, p->data_); p->is_dirty_ = false; } // erase the pagetable_. page_table_.erase(p->page_id_); } } else { //found: fid = free_list_.front(); free_list_.pop_front(); p = &pages_[fid]; } // Step 3. page_table_[page_id] = fid; replacer_->Pin(fid); // Step 4. p->page_id_ = page_id; p->pin_count_ = 1; disk_manager_->ReadPage(page_id, p->data_); latch_.unlock(); return p; }
3、DeletePgImp函数
这个函数要求我们删除某个页.当然,代码的注释也给出了很详细的说明.
首先判断要删除的那个页到底存不存在,如果不存在的话就跳过,然后判断被删除的那个页到底有没有被Pin,如果被Pin了的话也是不能删除的,接着判断这个页是不是为脏,如果是脏页就要写回,最后把这个页的一些信息初始化,然后把这个页的信息加入到freelist里面.
bool BufferPoolManagerInstance::DeletePgImp(page_id_t page_id) { // 0. Make sure you call DeallocatePage! // 1. Search the page table for the requested page (P). // 1. If P does not exist, return true. // 2. If P exists, but has a non-zero pin-count, return false. Someone is using the page. // 3. Otherwise, P can be deleted. Remove P from the page table, reset its metadata and return it to the free list. if (page_table_.find(page_id) == page_table_.end()) { return true; } // P does exists. frame_id_t fid = page_table_[page_id]; Page* deletepage = &pages_[fid]; // P is pinned if (deletepage->pin_count_ != 0) { return false; } // if dirty rewrite: // flush the page before deallocate it. latch_.lock(); if (deletepage->is_dirty_) { disk_manager_->WritePage(page_id, deletepage->data_); deletepage->is_dirty_ = false; } DeallocatePage(page_id); // remove P from the page table. page_table_.erase(page_id); // reset its metadata. // the page returned to freelist does not stores any page. deletepage->page_id_ = INVALID_PAGE_ID; deletepage->is_dirty_ = false; deletepage->pin_count_ = 0; // return it to free_list_. free_list_.push_back(fid); latch_.unlock(); return true; }
好了,最难的几个函数我们都做完了,剩下的几个都比较简单.
4、FlushPgImp函数
刷新一个页,把这个页里面的数据写入磁盘.
找到这个页,然后调用WritePage就可以了.
bool BufferPoolManagerInstance::FlushPgImp(page_id_t page_id) { // Make sure you call DiskManager::WritePage! std::lock_guard<std::mutex> lock(latch_); if (page_table_.find(page_id) == page_table_.end() || page_id == INVALID_PAGE_ID) return false; disk_manager_->WritePage(page_id, pages_[page_table_[page_id]].data_); return true; }
5、UnpinPgImp函数
让一个页的pin数减1.
找到一个页,首先置脏位,然后让pin数-1,如果减为0就调用Replacer的Unpin函数.
bool BufferPoolManagerInstance::UnpinPgImp(page_id_t page_id, bool is_dirty) { std::lock_guard<std::mutex> lock(latch_); frame_id_t fid = page_table_[page_id]; Page* p = &pages_[fid]; p->is_dirty_ = is_dirty; // hold the state until victim. if (p->pin_count_ <= 0) return false; --p->pin_count_; if (p->pin_count_ == 0) { replacer_->Unpin(fid); return true; } return false; }

实验1.3 PARALLEL BUFFER POOL MANAGER
并行的manager,先前是一个manager工作,现在是多个manager工作,具体的思路大同小异,就是先选择究竟是哪一个manager,然后再调用这个manager的函数.
选择的方式比较淳朴,假设有N个manager,那个调用manager的序号就是id % N.
这一部分的函数,除了创建新页面这个不确定初始页面id的情况下,其他的都一模一样.
1、NewPgImp函数.
遍历一遍所有的Manager,然后调用所有的Manager的NewPgImp函数,找得到就返回,找不到就算了,返回空指针吧.
Page *ParallelBufferPoolManager::NewPgImp(page_id_t *page_id) { // create new page. We will request page allocation in a round robin manner from the underlying // BufferPoolManagerInstances // 1. From a starting index of the BPMIs, call NewPageImpl until either 1) success and return 2) looped around to starting index and return nullptr // 2. Bump the starting index (mod number of instances) to start search at a different BPMI each time this function is called for(size_t i = 0; i < num_instances_; i++){ BufferPoolManager* one_manager_instance = manager_[next_instacnce_]; Page *page = one_manager_instance->NewPage(page_id); if(page != nullptr){ return page; } next_instacnce_ = (next_instacnce_ + 1) % num_instances_; } return nullptr; }
当然,有小伙伴就问了,你这样子做,有没有这样一种可能,就是生成这个页的时候是由i号Manager生成的,但是调用这个页的时候是由j号Manager管理,这个可以说应该是不可能的,因为next_instacnce_可以认为是和page_id同步的(起码模 N是一样的),各位做实验可以验证这个结论.
2、其他函数.
先选Manager,再调用,没啥好说的.
BufferPoolManager *ParallelBufferPoolManager::GetBufferPoolManager(page_id_t page_id) { // Get BufferPoolManager responsible for handling given page id. You can use this method in your other methods. return manager_[page_id % num_instances_]; } Page *ParallelBufferPoolManager::FetchPgImp(page_id_t page_id) { // Fetch page for page_id from responsible BufferPoolManagerInstance return GetBufferPoolManager(page_id)->FetchPage(page_id); } bool ParallelBufferPoolManager::UnpinPgImp(page_id_t page_id, bool is_dirty) { // Unpin page_id from responsible BufferPoolManagerInstance return GetBufferPoolManager(page_id)->UnpinPage(page_id,is_dirty); } bool ParallelBufferPoolManager::FlushPgImp(page_id_t page_id) { // Flush page_id from responsible BufferPoolManagerInstance return GetBufferPoolManager(page_id)->FlushPage(page_id); }

Lab2.EXTENDIBLE HASH INDEX
概要

左边那个就是directory page,它有一个参数叫做global depth,1<<global depth为directory的大小。它存储了指向各个bucket page的指针。bucket page里面存储的则是实际的数据(在本实验中是std::pair类型的键值),每个bucket都有一个自己的local depth。
插入一个键值的过程是:先把key代入hash函数计算得到一个中间结果,取这个中间结果的最后global depth位(这就是global depth mask的作用,就是 数据&global mask(具体请看下面的例子) ),得到一个数组下标,bucket的page id就在这个下标里。根据page id调入bucket,然后把这个键值插入到bucket里面。
实验2.1 PAGE LAYOUTS
提示:完成两种页的设计,一个是桶一个是目录.
修改src/include/storage/page/hash_table_bucket_page.h、src/storage/page/hash_table_bucket_page.cpp、src/include/storage/page/hash_table_directory_page.h和src/storage/page/hash_table_directory_page.cpp
实验2.1.1 目录页的设计
我们先来看看头文件(头文件不需要修改)
page_id_t page_id_; // 页的id lsn_t lsn_; uint32_t global_depth_{0};//全局深度,也就是说下面的数组有几个元素.2^i的关系,所有局部深度不能比全局深度大 uint8_t local_depths_[DIRECTORY_ARRAY_SIZE];//每一个页的局部深度,这个类似三级页表.第一级的页表局部深度就是2.局部深度代表你作为目录项离叶结点(bucket有多远) page_id_t bucket_page_ids_[DIRECTORY_ARRAY_SIZE];//下一级的页号
1、GetGlobalDepthMask函数
这个函数要求我们返回一个掩码,掩码的概念我们在计算机网络中学过,对于网络地址,网络地址有几位,就有几个1,在这里,全局深度为几就有几个1.
uint32_t HashTableDirectoryPage::GetGlobalDepthMask() { uint32_t global_depth_mask = ((1 << GetGlobalDepth()) - 1); return global_depth_mask; }
2、IncrGlobalDepth函数
这需要我们增长全局深度,根据CMU的PPT里面介绍,我们不仅要增加变量的值(value),还需要进行local_depths和bucket的初始化.初始化的方法就是1:1复制,因为这种增长是成倍增长的,对于1~N的节点,给N+1~2N赋值的时候直接完全复制就可以了.
void HashTableDirectoryPage::IncrGlobalDepth() { int original_depth = 1 << global_depth_; int new_index = original_depth; for(int i = 0;i < original_depth;i++){ local_depths_[new_index] = local_depths_[i]; bucket_page_ids_[new_index] = bucket_page_ids_[i]; new_index++; } global_depth_++; }
3、CanShrink函数
能否缩小全局变量,那就判断有没有一个局部深度比全局深度深.
bool HashTableDirectoryPage::CanShrink() { int original_depth = 1 << global_depth_; for(int i = 0;i < original_depth;i++){ if(local_depths_[i] >= global_depth_) return false; } return true; }
其他的函数都是set和get,相信各位都可以做出来.
2.1.2 桶页的设计
首先我们来看头文件:
// For more on BUCKET_ARRAY_SIZE see storage/page/hash_table_page_defs.h char occupied_[(BUCKET_ARRAY_SIZE - 1) / 8 + 1]; // 0 if tombstone/brand new (never occupied), 1 otherwise. char readable_[(BUCKET_ARRAY_SIZE - 1) / 8 + 1]; MappingType array_[0];
首先就是MappingType,保存了一系列键值对,还有一个bitmap,来表示占用与存储有效信息.
1、可读和占用的判断和设置
这个bitmap是一个char[]的数组,首先我们要判断出它们是在数组的哪一个元素,然后从这个元素中进行恰当的位运算.int A = id/8(哪一个元素) int B = id % 8(这个元素的哪一位),这个就很像xv6文件系统中的bitmap.
然后就是设置,设置的思路其实也是一样的,找到位置和具体哪一位,然后置0或者是1,大体上类似于get和set,但是有一点不一样的就是set和get的粒度是具体到bit的,这个需要我们使用正确且高效的位运算.
template <typename KeyType, typename ValueType, typename KeyComparator> bool HASH_TABLE_BUCKET_TYPE::IsOccupied(uint32_t bucket_idx) const { size_t c = occupied_[bucket_idx / 8]; c = c & (1 << (bucket_idx % 8)); return c != 0; } template <typename KeyType, typename ValueType, typename KeyComparator> void HASH_TABLE_BUCKET_TYPE::SetOccupied(uint32_t bucket_idx) { size_t c = occupied_[bucket_idx / 8]; c = c | (1 << (bucket_idx % 8)); occupied_[bucket_idx / 8] = static_cast<char>(c); } template <typename KeyType, typename ValueType, typename KeyComparator> bool HASH_TABLE_BUCKET_TYPE::IsReadable(uint32_t bucket_idx) const { size_t c = readable_[bucket_idx / 8]; c = c & (1 << (bucket_idx % 8)); return c != 0; } template <typename KeyType, typename ValueType, typename KeyComparator> void HASH_TABLE_BUCKET_TYPE::SetReadable(uint32_t bucket_idx) { size_t c = readable_[bucket_idx / 8]; c = c | (1 << (bucket_idx % 8)); readable_[bucket_idx / 8] = static_cast<char>(c); }
还记得我们在大一做的C语言位运算的题目嘛?这下用上了.
2、Remove系列函数
首先基础的函数就是RemoveAt函数,RemoveAt函数其实类似于SetReadable(i,0).接着就是Remove,基本思路就是比较,找到匹配的值然后删除掉即可.
其实可以思考一下,为什么Key类型的需要使用比较器,但是Value的值不需要比较器,为什么设置的模版只有3个参数.
template <typename KeyType, typename ValueType, typename KeyComparator> bool HASH_TABLE_BUCKET_TYPE::Remove(KeyType key, ValueType value, KeyComparator cmp) { for(size_t i = 0; i < BUCKET_ARRAY_SIZE ; i++){ if(IsReadable(i)){ if(cmp(key,array_[i].first) == 0 && value == array_[i].second){ RemoveAt(i); return true; } } } return false; } template <typename KeyType, typename ValueType, typename KeyComparator> void HASH_TABLE_BUCKET_TYPE::RemoveAt(uint32_t bucket_idx) { size_t c = readable_[bucket_idx / 8]; c = c & (~(1 << (bucket_idx % 8))); readable_[bucket_idx / 8] = static_cast<char>(c); }
3、是否全满,是否全空.
这类思路都是一样的,对于bitmap的全部数据,进行遍历.只不过这一次遍历的粒度不需要下降到位的级别,只需要看看,char[]里面的值是不是全0或者是全1,这下我们可以使用mask=0xFF来进行与或运算.
这时候有小伙伴会问,万一桶的元素不为8的整数,剩下的5个怎么比较呢?我们可以把最后一个char类型的元素取出来,然后可以利用10000000取高位来进行取值.
template <typename KeyType, typename ValueType, typename KeyComparator> bool HASH_TABLE_BUCKET_TYPE::IsEmpty() { u_int8_t mask = 0; size_t times = BUCKET_ARRAY_SIZE / 8; for (size_t i = 0; i < times; i++) { char c = readable_[i]; uint8_t ic = static_cast<uint8_t>(c); if ((ic | mask) != mask) { return false; } } //剩下的 size_t remain = BUCKET_ARRAY_SIZE % 8; if (remain > 0) { char c = readable_[times]; uint8_t ic = static_cast<uint8_t>(c); for (size_t i = 0; i < remain; i++) { //每次取1位 if ((ic & 1) != 1) { return false; } //迭代 ic = ic >> 1; } } return true; }
实验2.2 HASH TABLE IMPLEMENTATION
0、概要
这一个部分我们需要结合之前的BufferPoolManager来完善哈希表的增删改查的操作.
初始情况下global depth为0,directory大小为1<<0=1,因此只有一个bucket,此bucket的local depth为0。这时插入键值,取哈希函数中间结果的后0位,得到的directory下标总是为0,所有的元素全进入这个初始bucket。
如果一个桶满了,就需要分裂成两个桶,分裂的伪代码如下:
split--伪代码 bucket_page = Fetch(bucket_idx); if(bucket为空){ 构造分裂映像 split_page = NewPage(&split_idx); if(全局深度 == 局部深度){ 需要增长目录; 产生的许多空索引需要进行填入page_id信息以及局部深度信息 指向相同的page_id的索引之间相差了1<<(全局深度); 修改目录的信息以及设置分裂后的桶的相关信息 }else{ 仅需要分裂桶; 先增加局部深度,接着确定兄弟索引的个数; 修改分裂后兄弟索引的指向; } 分配旧桶里面的数据,一般会均分到两个桶里面 } 执行插入即可
下面用图片介绍一下分裂的内容.
假设global_depth=1,就是两个桶:(目录桶对应的是key的最后一位)

假设桶b满了,这个时候local_depth=1=global_depth.这个时候目录页需要扩充.
桶b的内容(1),平均分成01和11.桶a的内容被00和10指着

这个时候local_depth变成了2,原来的a桶depth还是1.

如果a满了,也是一样分裂,但是local_depth=1<2,目录页是不用分裂的.
插入讲完了,现在我们需要讲一讲合并.
在删除bucket_page 000 后,如果这里的000空了,空了就尝试merge。参考官方做法就是:
(1)两哈希桶均为空桶;
(2)目录项及其目标目录项(一个目录项的目标目录项可由其低第j
位反转得到)的局部深度相同且不为0。
满足上述两个条件后就可以进行合并了。
1、查(getValue)
了解一下函数的做法首先第一步获取目录页,然后根据目录页调用KeyToPageId获取具体位于哪一个桶里面.然后调用getdata和getvalue函数进行查找.查找的返回值是有没有查找到相关信息,查找的结果返回在result变量里面.(注意page只是一个指针,你还是需要通过GetData来获得指针里面具体指向的内容),注意在最后需要调用unpin函数取消对页的pin.
template <typename KeyType, typename ValueType, typename KeyComparator> bool HASH_TABLE_TYPE::GetValue(Transaction *transaction, const KeyType &key, std::vector<ValueType> *result) { table_latch_.RLock(); HashTableDirectoryPage *dir_page = FetchDirectoryPage(); page_id_t bucket_page_id = KeyToPageId(key,dir_page); Page* page = FetchBucketPage(bucket_page_id); page->RLatch(); HASH_TABLE_BUCKET_TYPE *bucket_page = reinterpret_cast<HASH_TABLE_BUCKET_TYPE*>(page->GetData()); bool res = bucket_page->GetValue(key,comparator_,result); page->RUnlatch(); buffer_pool_manager_->UnpinPage(directory_page_id_,false); buffer_pool_manager_->UnpinPage(bucket_page_id,false); table_latch_.RUnlock(); return res; }
2、增(Insert)
这是基本的插入操作.基本的操作还是和之前一样,获取目录,根据目录来获取桶,如果这个桶没有满的话,那么就可以直接调用桶页的相关操作,然后Unpin,返回即可.但是万一桶是满的怎么办,请往下看.
template <typename KeyType, typename ValueType, typename KeyComparator> bool HASH_TABLE_TYPE::Insert(Transaction *transaction, const KeyType &key, const ValueType &value) { table_latch_.WLock(); HashTableDirectoryPage* dir_page = FetchDirectoryPage(); page_id_t bucket_page_id = KeyToPageId(key,dir_page); Page* page = FetchBucketPage(bucket_page_id); page->WLatch(); HASH_TABLE_BUCKET_TYPE* bucket_page = reinterpret_cast<HASH_TABLE_BUCKET_TYPE*>(page->GetData()); bool flag = bucket_page->IsFull(); if(!flag){ bool ret = bucket_page->Insert(key,value,comparator_); page->WUnlatch(); buffer_pool_manager_->UnpinPage(bucket_page_id,true); buffer_pool_manager_->UnpinPage(dir_page->GetPageId(),false); table_latch_.WUnlock(); return ret; } page->WUnlatch(); buffer_pool_manager_->UnpinPage(bucket_page_id,false); buffer_pool_manager_->UnpinPage(dir_page->GetPageId(),false); table_latch_.WUnlock(); return SplitInsert(transaction,key,value); }
3、可扩展的增(Insert)
对于一个比较大而且满的页,一个比较直观的想法就是分裂成两个页,这两个页都可以继续执行插入操作.这个操作比较复杂,在这里我就只用分步的形式来进行描述.
- 跟前几个函数一样,首先获取要分裂的页.(这个页就是key对应的上一层的目录页)
- 如果这个页的深度已经到达了最大深度,那么就不能再分裂下去,返回false.
- 如果这个页和全局深度一样,就增加一下全局深度.
- 然后获取这个桶里面的所有元素以及元素的数量.
- 然后构造(申请一个新的)镜像页,把镜像页的基本信息写入到目录页里面,比如说页的局部深度以及ID等等.
4、删(Remove)
删除一个键值对.
首先还是基础操作,获取桶页,然后调用remove函数就可以了.
template <typename KeyType, typename ValueType, typename KeyComparator> bool HASH_TABLE_TYPE::Remove(Transaction *transaction, const KeyType &key, const ValueType &value) { table_latch_.RLock(); HashTableDirectoryPage* dir_page = FetchDirectoryPage(); uint32_t bucket_page_id = KeyToPageId(key,dir_page); Page* page = FetchBucketPage(bucket_page_id); page->WLatch(); HASH_TABLE_BUCKET_TYPE* bucket_page = reinterpret_cast<HASH_TABLE_BUCKET_TYPE*>(page->GetData()) ; bool ret = bucket_page->Remove(key,value,comparator_); page->WUnlatch(); buffer_pool_manager_->UnpinPage(dir_page->GetPageId(),false); buffer_pool_manager_->UnpinPage(bucket_page_id,true); table_latch_.RUnlock(); if(bucket_page->IsEmpty()){ Merge(transaction,key,value); return ret; } return ret; }
5、合并(Merge)
删除了一个元组之后有可能产生空页,空页是没有意义的,要把空页和相对应的页做一个merge操作,合并在一起.
0 条评论