数据库任务一存储管理

任务1.1 缓冲池管理器

任务1.1.1 磁盘存储管理器

任务要求

本任务要求补全DiskManager类，其负责读写指定页面、分配页面编号，以及对文件进行操作。

DiskManager类的接口如下：

class DiskManager {
   public:
    explicit DiskManager();        // Constructor
    ~DiskManager() = default;    // Destructor
    // 读写页面
    void write_page(int fd, page_id_t page_no, const char *offset, int num_bytes);
    void read_page(int fd, page_id_t page_no, char *offset, int num_bytes);
    // 对指定文件分配页面编号
    page_id_t AllocatePage(int fd);
    // 文件操作
    bool is_file(const std::string &path);
    void create_file(const std::string &path);
    int open_file(const std::string &path);
    void close_file(int fd);
    void destroy_file(const std::string &path);
}

通关截图

代码分析

write_page函数

/**
 * @brief Write the contents of the specified page into disk file
 *
 */
void DiskManager::write_page(int fd, page_id_t page_no, const char *offset, int num_bytes) {
    // Todo:
    // 1.lseek()定位到文件头，通过(fd,page_no)可以定位指定页面及其在磁盘文件中的偏移量
    // 2.调用write()函数
    // 注意处理异常
    lseek(fd, page_no*PAGE_SIZE, SEEK_SET);
    ssize_t bytes_write = write(fd, offset, num_bytes);
    if (bytes_write != num_bytes) {
        throw UnixError();
    }
}

lseek头文件以及函数声明如下

1
2
3

#include <sys/types.h>
#include <unistd.h>
off_t lseek(int fd, off_t offset, int whence);

代码内的lseek()函数会重新定位被打开文件的位移量，根据参数offset以及whence的组合来决定。

offset为正则向文件末尾移动，为负数则向文件头部。

SEEK_SET：从文件头部开始偏移offset个字节。

SEEK_CUR：从文件当前读写的指针位置开始，增加offset个字节的偏移量。

SEEK_END：文件偏移量设置为文件的大小加上偏移量字节。

write函数头文件以及函数声明如下

1 2	#include <unistd.h> ssize_t write(int fd, const void *buf,size_t nbytes)

fd为文件描述符，buf：指定的缓冲区，即指针，指向一段内存单元，nbytes：要写入文件指定的字节数。返回值：成功时写入文档的字节数，出错时返回-1。

代码中对写函数的返回值进行判断，如果实际写的字节数不等于要求写的字节数，则报错。

read_page函数

**
 * @brief Read the contents of the specified page into the given memory area
 */
void DiskManager::read_page(int fd, page_id_t page_no, char *offset, int num_bytes) {
    // Todo:
    // 1.lseek()定位到文件头，通过(fd,page_no)可以定位指定页面及其在磁盘文件中的偏移量
    // 2.调用read()函数
    // 注意处理异常
    lseek(fd, page_no*PAGE_SIZE, SEEK_SET);
    ssize_t bytes_read = read(fd, offset, num_bytes);
    if (bytes_read != num_bytes) {
        throw UnixError();
    }
}

read函数与write函数相像，其头函数和函数声明如下

1 2	#include <unistd.h> ssize_t read(int fd, void *buf, size_t count);

返回值：成功返回读取的字节数，出错返回-1并设置errno。如果在调read之前已到达文件末尾，则这次read返回0

AllocatePage函数

/**
 * @brief Allocate new page (operations like create index/table)
 * For now just keep an increasing counter
 */
page_id_t DiskManager::AllocatePage(int fd) {
    // Todo:
    // 简单的自增分配策略，指定文件的页面编号加1
    fd2pageno_[fd]++;
	return fd2pageno_[fd]-1;
}

根据disk_manager.h中fd2pageno_[fd]代表着文件fd中分配的page no个数，这里采用简单的自增分配策略，指定文件页面编号加一。

is_file函数

/**
 * @brief 用于判断指定路径文件是否存在 
 */
bool DiskManager::is_file(const std::string &path) {
    // Todo:
    // 用struct stat获取文件信息
    struct stat st;
    int rc = stat(path.c_str(), &st);
    return rc == 0 ? true : false;
}

.c_str()函数将string格式的path转换成char格式

stat函数头文件和定义函数如下所示

1
2
3

#include <sys/stat.h>
#include <unistd.h>
int stat(const char *file_name, struct stat *buf);

通过文件名filename获取文件信息，并保存在buf所指的结构体stat中

返回值：执行成功则返回0，失败返回-1，错误代码存于errno

利用stat函数的返回值判断是否执行成功，成功则说明指定路径文件存在。

create_file函数

/**
 * @brief 用于创建指定路径文件
 */
void DiskManager::create_file(const std::string &path) {
    // Todo:
    // 调用open()函数，使用O_CREAT模式
    // 注意不能重复创建相同文件
    if(is_file(path)){
		throw FileExistsError(path);
	}
    int fd = open(path.c_str(), O_WRONLY | O_CREAT);
    if(fd < 0)
		throw UnixError();	
	close(fd);
}

首先判断路径文件是否存在，存在则报错

open函数头函数和定义函数

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int open(const char *pathname, int flags);
int open(const char *pathname, int flags, mode_t mode);

返回值：open函数的返回值如果操作成功，它将返回一个文件描述符，如果操作失败，它将返回-1。如果操作失败则抛出异常。并在操作后关闭open。

flags参数表示打开文件所采用的操作，我们需要注意的是：必须指定以下三个常量的一种，且只允许指定一个（ubuntu 20.04不加下面三个也没报错）

O_RDONLY：只读模式
O_WRONLY：只写模式
O_RDWR：可读可写

以下的常量是选用的，这些选项是用来和上面的必选项进行按位或起来作为flags参数。

O_APPEND 表示追加，如果原来文件里面有内容，则这次写入会写在文件的最末尾。
O_CREAT 表示如果指定文件不存在，则创建这个文件
O_EXCL 表示如果要创建的文件已存在，则出错，同时返回 -1，并且修改 errno 的值。
O_TRUNC 表示截断，如果文件存在，并且以只写、读写方式打开，则将其长度截断为0。
O_NOCTTY 如果路径名指向终端设备，不要把这个设备用作控制终端。
O_NONBLOCK 如果路径名指向 FIFO/块文件/字符文件，则把文件的打开和后继 I/O设置为非阻塞模式（nonblocking mode）

destroy_file函数

/**
 * @brief 用于删除指定路径文件 
 */
void DiskManager::destroy_file(const std::string &path) {
    // Todo:
    // 调用unlink()函数
    // 注意不能删除未关闭的文件
    if(!is_file(path)){
		throw FileNotFoundError(path);
	}
    if(path2fd_.find(path) != path2fd_.end()){
        throw UnixError();
    }
    int ret = unlink(path.c_str());
    if (ret < 0) {
        throw UnixError();
    }
}

浏览find函数的文档

可以知道find可以在unordered_map中进行查找，当数据出现时，返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器。则可以用path2fd_.find(path) != path2fd_.end()来判断哈希表数据不存在。

查看disk_manager.h定义，path2fd_和fd2path_用于记录文件是否被打开，注意不能重复打开相同文件，如果能够找到记录数据，则抛出异常。

unlink函数头文件和声明函数如下

1 2	#include<unistd.h> int unlink(const char* pathname);

unlink从文件系统中中删除一个名字，若这个名字是指向这个文件的最后一个链接，并且没有进程处于打开这个文件的状态，则删除这个文件，释放这个文件占用的空间。如果这个名字是指向这个文件的最后一个链接，但有某个进程处于打开这个文件的状态，则暂时不删除这个文件，要等到打开这个文件的进程关闭这个文件的文件描述符后才删除这个文件。

返回值：调用成功返回0，不成功返回-1。如果不成功则抛出异常。

open_file函数

/**
 * @brief 用于打开指定路径文件
 */
int DiskManager::open_file(const std::string &path) {
    // Todo:
    // 调用open()函数，使用O_RDWR模式
    // 注意不能重复打开相同文件，并且需要更新文件打开列表
    if(!is_file(path)){
		throw FileNotFoundError(path);
	}
    if(path2fd_.find(path) != path2fd_.end()){
        throw UnixError();
    }
    int fd = open(path.c_str(), O_RDWR);
    if (fd < 0) {
        throw UnixError();
    }
    path2fd_.insert(std::make_pair(path, fd));
	fd2path_.insert(std::make_pair(fd,path));
    return fd;
}

同理，文件路径不存在则抛出异常，文件已经被打开则抛出异常，如果打开文件失败则抛出异常。

打开文件后，在path2fd_和fd2path_表中更新打开记录。

close_file函数

/**
 * @brief 用于关闭指定路径文件
 */
void DiskManager::close_file(int fd) {
    // Todo:
    // 调用close()函数
    // 注意不能关闭未打开的文件，并且需要更新文件打开列表
    if(fd2path_.find(fd) == fd2path_.end()){
		throw FileNotOpenError(fd);
	}
	path2fd_.erase(fd2path_[fd]);
	fd2path_.erase(fd);
	close(fd);
}

同理，查找fd2path_或path2fd_表判断是否已经打开，如果没有打开记录则抛出异常。

关闭文件，清空表中的记录，关闭open状态。

任务1.1.2 缓冲池替换策略

任务要求

本任务要求补全Replacer类，其负责跟踪缓冲池中每个页面所在帧的使用情况。当缓冲池没有空闲页面时，需要使用该类提供的替换策略选择一个页面进行淘汰。要求实现的替换策略为最近最少使用（LRU）算法。

Replacer类的接口如下：

class Replacer {
   public:
    explicit Replacer(size_t num_pages);
    ~Replacer();
    bool Victim(frame_id_t *frame_id);
    void Pin(frame_id_t frame_id);
    void Unpin(frame_id_t frame_id);
};

通关截图

代码分析

Victim函数

/**
 * @brief 使用LRU策略删除一个victim frame，这个函数能得到frame_id
 * @param[out] frame_id id of frame that was removed, nullptr if no victim was found
 * @return true if a victim frame was found, false otherwise
 */
bool LRUReplacer::Victim(frame_id_t *frame_id) {
    // C++17 std::scoped_lock
    // 它能够避免死锁发生，其构造函数能够自动进行上锁操作，析构函数会对互斥量进行解锁操作，保证线程安全。
    std::scoped_lock lock{latch_};

    // Todo:
    //  利用lru_replacer中的LRUlist_,LRUHash_实现LRU策略
    //  选择合适的frame指定为淘汰页面,赋值给*frame_id
    if(LRUlist_.size()!=0){
		*frame_id = LRUlist_.back();
		LRUlist_.pop_back();
		return true;
	}
	else {
        return false;
    }
}

std::scoped_lock lock{latch_};它能够避免死锁发生，其构造函数能够自动进行上锁操作，析构函数会对互斥量进行解锁操作，保证线程安全。

查看lru_replacer.h中LRUlist_的定义，发现其按照时间顺序排序，最近被访问过置于首部，最近未被访问的置于尾部。根据先来先淘汰的原则进行Victim操作并返回true，如果LRUlist_表中没有元素则不进行操作，返回false。

Pin函数

/**
 * @brief 固定一个frame, 表明它不应该成为victim（即在replacer中移除该frame_id）
 * @param frame_id the id of the frame to pin
 */
void LRUReplacer::Pin(frame_id_t frame_id) {
    std::scoped_lock lock{latch_};
    // Todo:
    // 固定指定id的frame
    // 在数据结构中移除该frame
	LRUlist_.remove(frame_id);
}

根据frame_id从LRUlist_去掉即可。

Unpin函数

/**
 * 取消固定一个frame, 表明它可以成为victim（即将该frame_id添加到replacer）
 * @param frame_id the id of the frame to unpin
 */
void LRUReplacer::Unpin(frame_id_t frame_id) {
    // Todo:
    //  支持并发锁
    //  选择一个frame取消固定
    int flag = 1; 
	latch_.lock();
	std::list<frame_id_t>::iterator it = LRUlist_.begin();
	while(it != LRUlist_.end()){
	    if(*it == frame_id){
	 		flag = 0;
	 		break;
	 	}
	 	++it;
	}
	if(flag){
        LRUlist_.push_front(frame_id);
    }
	latch_.unlock();
}

支持并发锁，函数运行过程中需要使用latch_.lock();和 latch_.unlock();上锁

取消固定frame，则需要将其重新添加至LRUlist_，但是有两种情况，一种是之前不存在，那么我们将frame添加至表头即可，但是如果之前存在，需要恢复至之前的位置。

Size函数

/** @return replacer中能够victim的数量 */
size_t LRUReplacer::Size() {
    // Todo:
    // 改写return size
    return LRUlist_.size();
}

返回LRUlist_此时的大小。

任务1.1.3 缓冲池管理器

任务要求

本任务要求补全BufferPoolManager类，其负责管理缓冲池中的页面与磁盘文件中的页面之间的来回移动。

BufferPoolManager类的接口如下：

class BufferPoolManager {
   public:
    BufferPoolManager(size_t pool_size, DiskManager *disk_manager);
    ~BufferPoolManager();
    Page *NewPage(PageId *page_id);
    Page *FetchPage(PageId page_id);
    bool UnpinPage(PageId page_id, bool is_dirty);
    bool DeletePage(PageId page_id);
    bool FlushPage(PageId page_id);
    void FlushAllPages(int fd);
   private:
    // 辅助函数
    bool FindVictimPage(frame_id_t *frame_id);
    void UpdatePage(Page *page, PageId new_page_id, frame_id_t new_frame_id);
}

通关截图

代码分析

FindVictimPage函数

/**
 * @brief 从free_list或replacer中得到可淘汰帧页的 *frame_id
 * @param frame_id 帧页id指针,返回成功找到的可替换帧id
 * @return true: 可替换帧查找成功 , false: 可替换帧查找失败
 */
bool BufferPoolManager::FindVictimPage(frame_id_t *frame_id) {
    // Todo:
    // 1 使用BufferPoolManager::free_list_判断缓冲池是否已满需要淘汰页面
    // 1.1 未满获得frame
    // 1.2 已满使用lru_replacer中的方法选择淘汰页面
    if(!free_list_.empty()){
        *frame_id = free_list_.front();
        free_list_.pop_front();
        return true;
    }
    else{
        return replacer_->Victim(frame_id);
    }
}

从buffer_pool_manager.h文件可知free_list_是空闲帧id组成的链表，如果这个链表为空，则说明缓冲池已满，使用replacer中的victim函数淘汰页面

如果缓冲池未满，则从free_list中获得可淘汰帧页，淘汰链表首部元素。

UpdatePage函数

/**
 * @brief 更新页面数据, 为脏页则需写入磁盘，更新page元数据(data, is_dirty, page_id)和page table
 *
 * @param page 写回页指针
 * @param new_page_id 写回页新page_id
 * @param new_frame_id 写回页新帧frame_id
 */
void BufferPoolManager::UpdatePage(Page *page, PageId new_page_id, frame_id_t new_frame_id) {
    // Todo:
    // 1 如果是脏页，写回磁盘，并且把dirty置为false
    // 2 更新page table
    // 3 重置page的data，更新page id
    if(page->is_dirty_){
        page->is_dirty_ = false;
        disk_manager_->write_page(page->GetPageId().fd, page->GetPageId().page_no, page->GetData(), PAGE_SIZE);
    }
    page_table_.erase(page->GetPageId());
    page_table_.insert(std::make_pair(new_page_id, new_frame_id));
    // if(new_page_id.page_no != INVALID_PAGE_ID){
	// 		page_table_.insert(std::make_pair(new_page_id, new_frame_id));
    // }
    page->ResetMemory();
    page->id_ = new_page_id;
}

在page.h文件中定义is_dirty_用于判断是否为脏页，调用即可。

如果是脏页，那么首先设为净页，并且写回磁盘，调用的是disk_manager中的write_page函数

清除旧页面并且将新页面添加进page_table_中，重置page的data，更新page id。

FetchPage函数

/**
 * Fetch the requested page from the buffer pool.
 * 如果页表中存在page_id（说明该page在缓冲池中），并且pin_count++。
 * 如果页表不存在page_id（说明该page在磁盘中），则找缓冲池victim page，将其替换为磁盘中读取的page，pin_count置1。
 * @param page_id id of page to be fetched
 * @return the requested page
 */
Page *BufferPoolManager::FetchPage(PageId page_id) {
    // Todo:
    // 0.     lock latch
    // 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.
    std::scoped_lock lock{latch_};
    std::unordered_map<PageId, frame_id_t, PageIdHash>::iterator it = page_table_.find(page_id);
    if(it != page_table_.end()){
        frame_id_t fid = it->second;
        replacer_->Pin(fid);
        pages_[fid].pin_count_++;
        return &pages_[fid];
    }
    else{
        frame_id_t frame_id = -1;
        if(!FindVictimPage(&frame_id)){
		    return nullptr;
        }
        Page *R = &pages_[frame_id];
        UpdatePage(R, page_id, frame_id);
        disk_manager_->read_page(page_id.fd, page_id.page_no, R->data_, PAGE_SIZE);
	    replacer_->Pin(frame_id);
	    R->pin_count_ = 1;
        return R;
        }
}

先上锁，std::scoped_lock lock{latch_};它能够避免死锁发生，其构造函数能够自动进行上锁操作，析构函数会对互斥量进行解锁操作，保证线程安全。

后在page_table_中查找page_id，如果it != page_table_.end()说明找到了，页表中存在page_id，该page在缓冲池中。对其进行Pin操作使其防止被替换掉，并且pin_count++。如果没找到，那么我们需要把他从磁盘中调出，并且淘汰缓冲池。检查是否为脏页，执行UpdatePage操作即可。腾出位置给该page，并对其进行Pin操作，初始化pin_count_为1。

UnpinPage函数

/**
 * Unpin the target page from the buffer pool. 取消固定pin_count>0的在缓冲池中的page
 * @param page_id id of page to be unpinned
 * @param is_dirty true if the page should be marked as dirty, false otherwise
 * @return false if the page pin count is <= 0 before this call, true otherwise
 */
bool BufferPoolManager::UnpinPage(PageId page_id, bool is_dirty) {
    // Todo:
    // 0. lock latch
    // 1. try to search page_id page P in page_table_
    // 1.1 P在页表中不存在 return false
    // 1.2 P在页表中存在 如何解除一次固定(pin_count)
    // 2. 页面是否需要置脏
    std::scoped_lock lock{latch_};
    std::unordered_map<PageId, frame_id_t, PageIdHash>::iterator it = page_table_.find(page_id);
    if(it == page_table_.end()){
        return false;
    }
    else{
        frame_id_t fid = it->second;
        Page *P = &pages_[fid];
        if(P->pin_count_ == 0){
		    return false;
        }
	    P->pin_count_ --;
	    if(P->pin_count_ == 0){
		    replacer_->Unpin(fid);
        }
	    if(is_dirty){
		    P->is_dirty_ = true;
        }
	    return true;
    }
}

先上锁，查询所给的page_id是否在页表中存在，如果不存在返回false，否则根据判断page的pin_count_的次数，如果UnPin前就为0则报错返回false，如果UnPin前为1执行操作后变为0，则将其放入replacer中的LRUlist_表中，否则不进行操作。使用id_dirty判断是否置脏。

FlushPage函数

/**
 * Flushes the target page to disk. 将page写入磁盘；不考虑pin_count
 * @param page_id id of page to be flushed, cannot be INVALID_PAGE_ID
 * @return false if the page could not be found in the page table, true otherwise
 */
bool BufferPoolManager::FlushPage(PageId page_id) {
    // Todo:
    // 0. lock latch
    // 1. 页表查找
    // 2. 存在时如何写回磁盘
    // 3. 写回后页面的脏位
    // Make sure you call DiskManager::WritePage!
    std::scoped_lock lock{latch_};
    std::unordered_map<PageId, frame_id_t, PageIdHash>::iterator it = page_table_.find(page_id);
    if(it == page_table_.end()){
        return false;
    }
    else{
        frame_id_t fid = it->second;
        Page *P = &pages_[fid];
        disk_manager_->write_page(P->GetPageId().fd, P->GetPageId().page_no, P->GetData(), PAGE_SIZE);
        P->is_dirty_ = false;
        return true;
    }
}

先上锁，在页表中查找，找不到返回false，如果找到则将其写回磁盘，并置净。

NewPage函数

/**
 * Creates a new page in the buffer pool. 相当于从磁盘中移动一个新建的空page到缓冲池某个位置
 * @param[out] page_id id of created page
 * @return nullptr if no new pages could be created, otherwise pointer to new page
 */
Page *BufferPoolManager::NewPage(PageId *page_id) {
    // Todo:
    // 0.   lock latch
    // 1.   Make sure you call DiskManager::AllocatePage!
    // 2.   If all the pages in the buffer pool are pinned, return nullptr.
    // 3.   Pick a victim page P from either the free list or the replacer. Always pick from the free list first.
    // 4.   Update P's metadata, zero out memory and add P to the page table. pin_count set to 1.
    // 5.   Set the page ID output parameter. Return a pointer to P.
    std::scoped_lock lock{latch_};
    frame_id_t fid = -1;
    page_id->page_no = disk_manager_->AllocatePage(page_id->fd);
    if (!FindVictimPage(&fid)) {
    	return nullptr;
    }
	Page *P = &pages_[fid];
	UpdatePage(P, *page_id, fid);
	replacer_->Pin(fid);
	P->pin_count_ = 1;
	return P;
}

上锁，分配新页面，检查缓冲池是否有空间进行淘汰，更新页面，进行Pin操作，设置为初始化1，之后将页面返回。

DeletePage函数

/**
 * @brief Deletes a page from the buffer pool.
 * @param page_id id of page to be deleted
 * @return false if the page exists but could not be deleted, true if the page didn't exist or deletion succeeded
 */
bool BufferPoolManager::DeletePage(PageId page_id) {
    // Todo:
    // 0.   lock latch
    // 1.   Make sure you call DiskManager::DeallocatePage!
    // 2.   Search the page table for the requested page (P).
    // 2.1  If P does not exist, return true.
    // 2.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.
    std::scoped_lock lock{latch_};
    std::unordered_map<PageId, frame_id_t, PageIdHash>::iterator it = page_table_.find(page_id);
    if(it == page_table_.end()){
        return true;
    }
    else{
        frame_id_t fid = it->second;
        Page *P = &pages_[fid];
        if(P->pin_count_ != 0){
            return false;
        }
        else{
            disk_manager_->DeallocatePage(page_id.page_no);
            page_id.page_no =  INVALID_PAGE_ID;
		    UpdatePage(P, page_id, fid);
		    free_list_.push_back(fid);
            return true;
        }
    }
    return false;
}

上锁，检查页面是否存在，如果不存在则说明已删除返回true，如果存在但是仍然处于pin状态，即pin_count_不为0，则失败返回false，否则移除释放页面空间，放回free_list_，操作成功返回true。

任务1.2 记录管理器

通关截图

任务1.2.1 记录操作

任务要求

本任务要求补全RMFileHandle类，其负责对文件中的记录进行操作。

每个RMFileHandle对应一个记录文件，当RMManager执行打开文件操作时，便会创建一个指向RMFileHandle的指针。

RMFileHandle类的接口如下：

class RmFileHandle {
   public:
    RmFileHandle(DiskManager *disk_manager, BufferPoolManager *buffer_pool_manager, int fd);
    // 不考虑事务的记录操作（事务将在后续实验使用）
    std::unique_ptr<RmRecord> get_record(const Rid &rid, Context *context) const;
    Rid insert_record(char *buf, Context *context);
    void delete_record(const Rid &rid, Context *context);
    void update_record(const Rid &rid, char *buf, Context *context);
    // 辅助函数
    RmPageHandle create_new_page_handle();
    RmPageHandle fetch_page_handle(int page_no) const;
    RmPageHandle create_page_handle();
    void release_page_handle(RmPageHandle &page_handle);
};

代码分析

get_record函数

/**
 * @brief 由Rid得到指向RmRecord的指针
 *
 * @param rid 指定记录所在的位置
 * @return std::unique_ptr<RmRecord>
 */
std::unique_ptr<RmRecord> RmFileHandle::get_record(const Rid &rid, Context *context) const {
    // Todo:
    // 1. 获取指定记录所在的page handle
    // 2. 初始化一个指向RmRecord的指针（赋值其内部的data和size）
    auto record = std::make_unique<RmRecord>(file_hdr_.record_size);
	RmPageHandle ph = fetch_page_handle(rid.page_no);
	char *slot = ph.get_slot(rid.slot_no);
    record->size = file_hdr_.record_size;
	memcpy(record->data, slot, record->size);
    return record;
}

insert_record函数

/**
 * @brief 在该记录文件（RmFileHandle）中插入一条记录
 *
 * @param buf 要插入的数据的地址
 * @return Rid 插入记录的位置
 */
Rid RmFileHandle::insert_record(char *buf, Context *context) {
    // Todo:
    // 1. 获取当前未满的page handle
    // 2. 在page handle中找到空闲slot位置
    // 3. 将buf复制到空闲slot位置
    // 4. 更新page_handle.page_hdr中的数据结构
    // 注意考虑插入一条记录后页面已满的情况，需要更新file_hdr_.first_free_page_no
    RmPageHandle ph = create_page_handle();
    int slot_no = Bitmap::first_bit(false, ph.bitmap, file_hdr_.num_records_per_page);
	Bitmap::set(ph.bitmap, slot_no);
	ph.page_hdr->num_records++;
	if (ph.page_hdr->num_records == file_hdr_.num_records_per_page) {
        file_hdr_.first_free_page_no = ph.page_hdr->next_free_page_no;
    }
	char *slot = ph.get_slot(slot_no);
	memcpy(slot, buf, file_hdr_.record_size);
    //Rid rid(ph.page->GetPageId().page_no, slot_no);
    return Rid{ph.page->GetPageId().page_no, slot_no};
}

delete_record函数

/**
 * @brief 在该记录文件（RmFileHandle）中删除一条指定位置的记录
 *
 * @param rid 要删除的记录所在的指定位置
 */
void RmFileHandle::delete_record(const Rid &rid, Context *context) {
    // Todo:
    // 1. 获取指定记录所在的page handle
    // 2. 更新page_handle.page_hdr中的数据结构
    // 注意考虑删除一条记录后页面未满的情况，需要调用release_page_handle()
    RmPageHandle ph = fetch_page_handle(rid.page_no);
    if (ph.page_hdr->num_records == file_hdr_.num_records_per_page) {
        release_page_handle(ph);
    }
    Bitmap::reset(ph.bitmap, rid.slot_no);
    ph.page_hdr->num_records--;
}

update_record函数

/**
 * @brief 更新指定位置的记录
 *
 * @param rid 指定位置的记录
 * @param buf 新记录的数据的地址
 */
void RmFileHandle::update_record(const Rid &rid, char *buf, Context *context) {
    // Todo:
    // 1. 获取指定记录所在的page handle
    // 2. 更新记录
    RmPageHandle ph = fetch_page_handle(rid.page_no);
    char *slot = ph.get_slot(rid.slot_no);
    memcpy(slot, buf, file_hdr_.record_size);
}

fetch_page_handle函数

/** -- 以下为辅助函数 -- */
/**
 * @brief 获取指定页面编号的page handle
 *
 * @param page_no 要获取的页面编号
 * @return RmPageHandle 返回给上层的page_handle
 * @note pin the page, remember to unpin it outside!
 */
RmPageHandle RmFileHandle::fetch_page_handle(int page_no) const {
    // Todo:
    // 使用缓冲池获取指定页面，并生成page_handle返回给上层
    // if page_no is invalid, throw PageNotExistError exception
    if(page_no >= file_hdr_.num_pages){
		throw PageNotExistError("name" ,page_no);
    }
    PageId page_id;
	page_id.fd = fd_;
	page_id.page_no = page_no;
    Page *page = nullptr;
    page = buffer_pool_manager_->FetchPage(page_id);
    RmPageHandle ph = RmPageHandle(&file_hdr_, page);
    return ph;
}

create_new_page_handle函数

/**
 * @brief 创建一个新的page handle
 *
 * @return RmPageHandle
 */
RmPageHandle RmFileHandle::create_new_page_handle() {
    // Todo:
    // 1.使用缓冲池来创建一个新page
    // 2.更新page handle中的相关信息
    // 3.更新file_hdr_
    PageId *page_id = new PageId;
	page_id->fd = fd_;
	Page *page = nullptr;
	page = buffer_pool_manager_->NewPage(page_id);
	RmPageHandle ph = RmPageHandle(&file_hdr_, page);
	ph.page_hdr->num_records = 0;
	ph.page_hdr->next_free_page_no = RM_NO_PAGE;
	Bitmap::init(ph.bitmap, file_hdr_.bitmap_size);
	file_hdr_.num_pages ++;
	file_hdr_.first_free_page_no = page->GetPageId().page_no;
    return ph;
}

create_page_handle函数

/**
 * @brief 创建或获取一个空闲的page handle
 *
 * @return RmPageHandle 返回生成的空闲page handle
 * @note pin the page, remember to unpin it outside!
 */
RmPageHandle RmFileHandle::create_page_handle() {
    // Todo:
    // 1. 判断file_hdr_中是否还有空闲页
    //     1.1 没有空闲页：使用缓冲池来创建一个新page；可直接调用create_new_page_handle()
    //     1.2 有空闲页：直接获取第一个空闲页
    // 2. 生成page handle并返回给上层
    if(file_hdr_.first_free_page_no == RM_NO_PAGE){
        return create_new_page_handle();
    }
    else{
        return fetch_page_handle(file_hdr_.first_free_page_no);
    }
}

release_page_handle函数

/**
 * @brief 当page handle中的page从已满变成未满的时候调用
 *
 * @param page_handle
 * @note only used in delete_record()
 */
void RmFileHandle::release_page_handle(RmPageHandle &page_handle) {
    // Todo:
    // 当page从已满变成未满，考虑如何更新：
    // 1. page_handle.page_hdr->next_free_page_no
    // 2. file_hdr_.first_free_page_no
    page_handle.page_hdr->next_free_page_no = file_hdr_.first_free_page_no;
	file_hdr_.first_free_page_no = page_handle.page->GetPageId().page_no;
}

任务1.2.2 记录迭代器

任务要求

本任务要求补全RmScan类，其用于遍历文件中存放的记录。

RmScan类继承于RecScan类，它们的接口如下：

class RecScan {
public:
    virtual ~RecScan() = default;
    virtual void next() = 0;
    virtual bool is_end() const = 0;
    virtual Rid rid() const = 0;
};

class RmScan : public RecScan {
public:
    RmScan(const RmFileHandle *file_handle);
    void next() override;
    bool is_end() const override;
    Rid rid() const override;
};

代码分析

RmScan函数

/**
 * @brief 初始化file_handle和rid
 *
 * @param file_handle
 */
RmScan::RmScan(const RmFileHandle *file_handle) : file_handle_(file_handle) {
    // Todo:
    // 初始化file_handle和rid（指向第一个存放了记录的位置）
    rid_ = Rid{RM_FIRST_RECORD_PAGE, -1};
    next();
}

next函数

/**
 * @brief 找到文件中下一个存放了记录的位置
 */
void RmScan::next() {
    // Todo:
    // 找到文件中下一个存放了记录的非空闲位置，用rid_来指向这个位置
    while (rid_.page_no < file_handle_->file_hdr_.num_pages) {
        RmPageHandle ph = file_handle_->fetch_page_handle(rid_.page_no);
        rid_.slot_no = Bitmap::next_bit(true, ph.bitmap, file_handle_->file_hdr_.num_records_per_page, rid_.slot_no);
        if (rid_.slot_no < file_handle_->file_hdr_.num_records_per_page) {
            return;
    	}
        rid_.slot_no = -1;
        rid_.page_no++;
    }
    rid_.page_no = RM_NO_PAGE;
}

is_end函数

/**
 * @brief  判断是否到达文件末尾
 */
bool RmScan::is_end() const {
    // Todo: 修改返回值
    return rid_.page_no == RM_NO_PAGE;
}

rid函数

/**
 * @brief RmScan内部存放的rid
 */
Rid RmScan::rid() const {
    // Todo: 修改返回值
    return rid_;
}

数据库任务一 存储管理

任务1.1 缓冲池管理器

任务1.1.1 磁盘存储管理器

任务要求

通关截图

代码分析

write_page函数

read_page函数

AllocatePage函数

is_file函数

create_file函数

destroy_file函数

open_file函数

close_file函数

任务1.1.2 缓冲池替换策略

任务要求

通关截图

代码分析

Victim函数

Pin函数

Unpin函数

Size函数

任务1.1.3 缓冲池管理器

任务要求

通关截图

代码分析

FindVictimPage函数

UpdatePage函数

FetchPage函数

UnpinPage函数

FlushPage函数

NewPage函数

DeletePage函数

任务1.2 记录管理器

通关截图

任务1.2.1 记录操作

任务要求

代码分析

get_record函数

insert_record函数

delete_record函数

update_record函数

fetch_page_handle函数

create_new_page_handle函数

create_page_handle函数

release_page_handle函数

任务1.2.2 记录迭代器

任务要求

代码分析

RmScan函数

next函数

is_end函数

rid函数

数据库任务一存储管理