cmu15445_labs

摘要:

cmu 15445课程实验笔记。特别鸣谢:西部小笼包。

Proj1 Buffer Pool

Task1 Extendible Hashing

  • For the first part of this project, you will build a general purpose hash table that uses unordered buckets to store unique key/value pairs. Your hash table must support the ability to insert/delete key/value entries without specifying the max size of the table. Your table needs to automatically grow in size as needed but you do not need shrink it. That is, you do not need to implement support for shrinking or compacting the hash table. You will also need to support checking to see whether a key exists in the hash table and return its corresponding value.

  • 代码一开始就创建了一个cmudb的namespace,平时都是用的std,所以查了下命名空间。

    在c++中,名称(name)可以是符号常量、变量、函数、结构、枚举、类和对象等等。工程越大,名称互相冲突性的可能性越大。另外使用多个厂商的类库时,也可能导致名称冲突。为了避免,在大规模程序的设计中,以及在程序员使用各种各样的C++库时,这些标识符的命名发生冲突,标准C++引入关键字namespace(命名空间/名字空间/名称空间),可以更好地控制标识符的作用域。命名空间只能在全局范围内定义,不能在某个函数内定义。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    //定义一个名字为A的命名空间(变量、函数)
    namespace A {
    int a = 100;
    }
    namespace B {
    int a = 200;
    }
    void test02()
    {
    //A::a a是属于A中
    cout<<"A中a = "<<A::a<<endl;//100
    cout<<"B中a = "<<B::a<<endl;//200
    }
  • 虚函数和纯虚函数的复习

    首先强调一个概念:

    定义一个函数为虚函数,不代表函数为不被实现的函数(虚函数是可以有函数体的)。

    定义他为虚函数是为了允许用基类的指针来调用子类的这个函数(允许多态)。

    定义一个函数为纯虚函数,才代表函数没有被实现,纯虚函数是为了实现一个接口起到规范作用。

  • 头文件中,在函数声明后面加上override有什呢

    1
    2
    3
    bool Find(const K &key, V &value) override;
    bool Remove(const K &key) override;
    void Insert(const K &key, const V &value) override;

    如果不使用override,当你手一抖,将foo()写成了f00()会怎么样呢?结果是编译器并不会报错,因为它并不知道你的目的是重写虚函数,而是把它当成了新的函数。如果这个虚函数很重要的话,那就会对整个程序不利。所以,override的作用就出来了,它指定了子类的这个虚函数是重写的父类的,如果你名字不小心打错了的话,编译器是不会编译通过的

  • 谷歌编程风格中,成员变量都是小写,并且会在成员变量名最后加上下划线

  • 我们先来讨论一种比较传统的哈希:哈希函数是目前的数值取余哈希表的大小。这种哈希有个问题就是,我们需要提前知道有多少元素,否则当我们需要扩容或者缩容时,整个哈希表都要进行重建。与此对应的是动态哈希。动态哈希可以根据需要进行扩容与缩容。一种动态哈希是我们常说的数组加链表的形式,我们将这种方法称为链式哈希。链式哈希的问题在于,某个桶中的链表可以无限增长,有可能导致不同的桶中的链表长度非常不均衡。(实际上,unordered_map在某个链长超过8时,会将链表转换为红黑树)。另一种动态哈希表时可扩展哈希表,也是本实验实现的哈希表。其原理如下图,当某个bucket满了的时候,会在必要的时候增加global,创建更多的bucket,然后将数据重新分配到不同的bucket,保证每个桶都还有位置。之所以要限制每个bucket的大小,是为了防止出现某个桶中元素过多,我们希望数据能够尽量均衡地分布在不同的桶中,使得查询速度比较稳定。每个bucket的内部维护了一个红黑树(map)。所以说unordered_map那种是数组+链表/红黑树,然后本实验这种是数组+红黑树。

  • const与mutable

    先来回顾下const的基础知识,const int * a是指针不能改变指向的那个内存位置的值,int * const a是指针不能指向其他位置。记忆方法就是,const离谁近(int & *)谁就不能变。

    const还可以用来修饰成员函数。类的成员函数后面加 const,表明这个函数不会对这个类对象的数据成员(准确地说是非静态数据成员)作任何改变。声明和定义时,都要在参数的圆括号后面加上const。与之对应的是mutable,被mutable修饰的成员变量,即使在const成员函数中,其值依然可以被改变。

  • 初始化列表的好处:成员变量如果有const或者引用,就必须用初始化列表而不能在构造函数里面赋值。即使没有const或者引用,使用初始化列表的效率也会更高。

  • make_shared函数可以返回一个指定类型的shared_ptr

    1
    2
    3
    std::shared_ptr<int> foo = std::make_shared<int> (10);
    // same as:
    std::shared_ptr<int> foo2 (new int(10));
  • 在定义一个普通类的某个成员函数时,我们需要

    1
    int Someclass::func()

    而如果是一个模板类,我们需要写全:

    1
    2
    template <typename K, typename V>
    int Someclass<K, V>::func()
  • C++11提供std::hash,在头文件中定义。

    1
    2
    template<class Key >
    struct hash;

    哈希模板定义一个函数对象,实现了散列函数。这个函数对象的实例定义一个operator(),即对()进行了重载,其功能是计算参数的hash值

    1。接受一个参数的类型Key.

    2。返回一个类型为size_t的值,表示该参数的哈希值.

    3。调用时不会抛出异常.

    4。若两个参数k1k2相等,则std::hash()(k1)== std::hash()(k2).

    5。若两个不同的参数k1k2不相等,则std::hash()(k1)== std::hash()(k2)成立的概率应非常小

  • 实验中,前面的图中最左边的数组中存储的是指向bucket的智能指针,将这个数组命名为buckets。buckets根据key计算出来的hash值的最后global_depth位(课件里面取得是前几位,这点实验实现方法与课件不同),将key和对应的value分到不同的bucket中。每个bucket里面都可能会有多个数据,这些数据存储在bucket中的map中,这个map的key和value就是原始的key和value。map的底层实现是红黑树,意味着每个bucket内部是维护了一个红黑树。分桶的依据是key的hash值。

    Insert过程如下图

    ![image-20211023152552705](/Users/zhangyazhe/Library/Application Support/typora-user-images/image-20211023152552705.png)

    ![image-20211023152604278](/Users/zhangyazhe/Library/Application Support/typora-user-images/image-20211023152604278.png)

    这个扩容可能一次还解决不了问题。比如BUCKET SIZE是2.
    有一个BUCKET里有 00110,00100(local depth 是2),你要插入的是00101
    先扩容一次,LOCAL DEPTH 变为3了,但是3个元素的头3位都是001,所以还是挤在一起了。所以要用WHILE 循环。
    直到有足够的空间可以放了为止。

  • map的erase函数可以返回指向被删除的元素的后面一个元素的迭代器

Task2 LRU Page Replacement Policy

  • This component is responsible for tracking the usage of pages in the buffer pool.

  • 第二个任务是实现一个LRU。通过一个哈希表和一个双向链表

    哈希表的key是元素的值,value是智能指针。双向链表的头部是刚刚被访问过的数据,tail部是最久没被访问的数据。当访问某个数据时,通过哈希表找到这个数据所在的节点,然后将这个节点移动到双向链表的头部。

Task3 Buffer Pool Manager

  • buffer pool的主要作用是,将page从数据库磁盘中取出到主存中

  • 主存和磁盘中的数据被分为固定大小的页。页可以存储元组、元数据、索引、日志记录等等。

  • 在DBMS中,有三种不同的page的概念:

    • Hardware Page(usually 4KB)
  • OS Page(4KB)

    • Database Page (1 - 16KB2)
  • 每个页中有meta_data和data,data就是这个页里面的实际数据,meta_data是一些描述这个页的信息。比如说pin_count的值是此时调用了这个页的线程数,is_dirty标志着这个页是否为脏页(脏页即页被读取到缓冲区并被修改,导致缓冲区中的数据与磁盘中的数据不一致),page_id是这个页的标识。在缓冲区中,数据也被按页进行管理。每次都是将一整个页从磁盘中读入主存(缓冲区)中。在bufferpool这个类中,有已下成员变量:pool_size是buffer pool的大小,说明了这个buffer pool中可以存放多少个page,page的指针数组,用来存放buffer pool中page的指针,page_table,一个哈希表,key是page_id,value是page_id对应页的指针,replacer,用来实现lru算法,free_list记录buffer pool中目前有多少页是空闲的。

    假如一个缓冲池中可以存放64个page,这些page一开始都是被存放在free_list中,可以理解为,缓冲池一开始就已经被page填满,只不过这时候的page是空的,一个page就像一个槽,可以被data和meta_data填充。

    FetchPage函数用来根据page_id取出一个page。这个page可能本来就存储在主存中(即存储在前面提到的page_table中),那直接从page_table里面找到他然后返回,并且需要将pin_count加一,意味着多了一个线程调用这个页。如果page不在主存中,就要去磁盘里面将这个页找到然后读入主存。在将这个page读入主存之前,需要先给这个page腾地方,如果free_list不为空,即buffer pool 还没满,那就直接从free_list里面取出一个page槽(其实是一个空的page),然后将从磁盘读出的数据写入这个空page中。如果free_list空了,意味着buffer pool满了,那就要用lru来踢掉buffer pool中的一个page。踢掉之前,如果被踢的page是脏的,那要先写回磁盘,然后再踢。

    什么时候一个page会被放进lru replacer呢?page刚被读出来的时候,pin_count大于0,意味着此时这个page正在被使用,这时候是不会将这个page加入replacer的。只有当一个page被使用完,他的pin_count等于0的时候,才会被放入replacer。

    其他的内容蛮简单的,看代码或者官网任务介绍就行了。

Proj2 B+ Tree

  • The second programming project is to implement an index in your database system. The index is responsible for fast data retrieval without having to search through every row in a database table, providing the basis for both rapid random lookups and efficient access of ordered records.

    You will need to implement B+Tree dynamic index structure. It is a balanced tree in which the internal pages direct the search and leaf pages contains actual data entries. Since the tree structure grows and shrink dynamically, you are required to handle the logic of split and merge. The project is comprised of the following three tasks:

  • 首先来看下B+树的查找、插入、删除都是怎么操作的。以课程作业的题目为例来说明。

    所以上面这题需要走4个指针。

    接下来,仍然是上面这个图,先做个假设:对于非叶子节点中的指针,比如10左右的两个指针,10左边的指针意思是<10,10右边的指针意思是>= 10。另一个假设是,当某个节点需要去隔壁节点借数时,优先从右边借。描述一下执行下面4个操作时树的变化:

    第一个:

    第二个:

    先找到18要插的叶子节点,随后发现满了。开始做分裂,前半部分和后半部分断开,后半部分的指针指到19.前半部分的指针指向后半部分。同时为了链接前半部分 和 后半部分,父亲节点需要多一个,以后半部分的第一个为值,插入父节点。

    第三个:

    借过来之后,需要把父亲节点更新为右边最左元素的值。

    第四个:

    首先删掉了31,没有元素可借,触发第一次合并。32到左边那里去,同时删掉父节点的30.
    随后父节点没元素了,,再次触发合并,合并用的是下面已经合并的那个节点的最左端的值,同时删除祖父节点26.

    接下来来看另外一个b+树,如下图所示。

    执行下面的两个操作,描述一下每个操作过程中,树是如何变化的

    第一个:

    第二个:

    总结一下:

    插入操作:如果有空位,直接插入。如果叶子节点满了,一个叶子节点分裂成两个。然后更新上面的非叶子节点。

    删除操作:如果删除后,叶子节点中元素数量只有(M-1)/2个,尝试从邻居的叶子节点借数,如果邻居借完之后也太少了,就不借了,直接合并。合并之后,父节点会删掉一个元素。注:M是指B+树的路数,上图中就是一个4路B+树。即,M = 每个节点的指针数

Task1 B+Tree Pages

  • 枚举类

    在标准C++中,枚举类型不是类型安全的。枚举类型被视为整数,这使得两种不同的枚举类型之间可以进行比较。

    C++11 引进了一种特别的 “枚举类”,可以避免上述的问题。使用 enum class 的语法来声明:
    enum class Enumeration{ Val1, Val2, Val3 = 100, Val4 /* = 101 */,};
    此种枚举为类型安全的。枚举类型不能隐式地转换为整数;也无法与整数数值做比较。

  • 代码里面每个节点名字都是page,所以下面的page其实就是节点

  • B+树的每一个page中,都存储着pair<KeyType, ValueType> array[]数组。对于根page和中间page,key是每个节点里面的那些数字(其实是主键的那些值),value是每个节点里面的那些“指针”,其实value并不是真的指针,value实际上是存储的page_id。对于根节点和中间节点,array[0]的key是弃用的,这样一来“指针”数就比key多一个。对于叶子节点,key是节点里面的那些数字(其实是主键的那些值),value是RID,不存在哪个空间被弃用。每个叶子leaf中还会存储下一个相邻节点的page_id,也类似于“指针”。所有page里面还存储着parent_page_id,记录着自己的父节点是谁

  • RID:即page_id + offset/slot。DBMS需要一种方法来追踪每一个元组(关系数据库中,一个元组就是表中的一行数据),最常用的方法就是使用RID即page_id + offset/slot定位。在讨论page内部的组织形式之前先来讨论一下DBMS是如何在磁盘上组织那些存储了page的文件的。组织方式主要有下面四种:

    其中,heap file organization就是我们实验中使用的,如下图所示

    维护了两个双向链表,分别保存的是未被使用的page和使用中的page。而对于log-structured file organization,DBMS只存储日志记录。我们接下来要介绍的使用page_id + slot的page结构不适用于log-structured file organization。

    slotted page结构如下图所示:

    这是一种最常见的page layout,header会记录目前有多少slot被使用了,还会记录上一个刚被使用的slot的开始的位置。通过page_id + slot就可以定位到一个tuple。tuple的结构如下图所示

  • B+树中的这些节点(page)也是通过buffer pool来管理的

  • 对于B+树中的页与磁盘中的页之间关系的思考:TODO

  • 在代码实现中,在b_plus_tree_page.h中定义的size是继承本类的中间节点和叶子节点中array数组的size。而max_size是中间节点实际能存储的key的个数。

Task2 B+ Tree Data Structure

  • 查找

    首先实现FetchPage函数,这个函数从bufferpool中取出page,并将其data转换成b+树的page。然后,在FindLeafPage中,根据key找叶子节点的代码,从根节点开始,根据key一层一层向下找。在每一层节点里面都使用二分查找。最后,在GetValue函数中,找到key所对应的value

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    /*
    * Find leaf page containing particular key, if leftMost flag == true, find
    * the left most leaf page
    */
    INDEX_TEMPLATE_ARGUMENTS
    B_PLUS_TREE_LEAF_PAGE_TYPE *BPLUSTREE_TYPE::FindLeafPage(const KeyType &key,
    bool leftMost) {
    if (IsEmpty()) return nullptr;
    //, you need to first fetch the page from buffer pool using its unique page_id, then reinterpret cast to either
    // a leaf or an internal page, and unpin the page after any writing or reading operations.
    auto pointer = FetchPage(root_page_id_);
    page_id_t next;
    for (page_id_t cur = root_page_id_; !pointer->IsLeafPage(); cur = next,pointer = FetchPage(cur)) {
    B_PLUS_TREE_INTERNAL_PAGE *internalPage = static_cast<B_PLUS_TREE_INTERNAL_PAGE *>(pointer);
    if (leftMost) {
    next = internalPage->ValueAt(0); // ValueAt返回array[0].second
    }else {
    next = internalPage->Lookup(key,comparator_); // LookUp中利用二分查找,返回array[i].second,其中array[i]是最后一个小于等于key的
    }
    buffer_pool_manager_->UnpinPage(cur,false);
    }
    return static_cast<B_PLUS_TREE_LEAF_PAGE_TYPE *>(pointer);
    }

    INDEX_TEMPLATE_ARGUMENTS
    BPlusTreePage *BPLUSTREE_TYPE::FetchPage(page_id_t page_id) {
    auto page = buffer_pool_manager_->FetchPage(page_id);
    return reinterpret_cast<BPlusTreePage *>(page->GetData());
    }

    /*
    * Return the only value that associated with input key
    * This method is used for point query
    * @return : true means key exists
    */
    INDEX_TEMPLATE_ARGUMENTS
    bool BPLUSTREE_TYPE::GetValue(const KeyType &key,
    std::vector<ValueType> &result,
    Transaction *transaction) {
    //step 1. find page
    B_PLUS_TREE_LEAF_PAGE_TYPE *tar = FindLeafPage(key);
    //step 2. find value
    result.resize(1);
    // 下面的LookUp函数,会在叶子节点里面找是否有key,如果有,就将对应的value存储在result[0]中,同时返回true,如果没找到key,就返回false
    auto ret = tar->Lookup(key,result[0],comparator_);
    //step 3. unPin buffer pool
    buffer_pool_manager_->UnpinPage(tar->GetPageId(), false);
    return ret;
    }
  • 删除

    根据key找到要删除数据所在的节点ni,如果这个节点删除数据后,剩余数据数量不小于节点最大容量的一半,就直接返回。如果小于了节点最大容量的一半,就要执行下面的操作:找到ni的sibling节点ns,判断ni和ns存储的数据量的和是否大于一个节点的最大容量,如果大于了,就将ns最前面的几个数据转移到ni最后面;如果不大于,就将ns与ni合并。当某个节点的size小于minSize时,就要调用函数ColasceOrRedistuibute(node),后面将这个函数简写为COR函数。如果node是根节点,就要再调用Ajust函数。这里解释下为什么根节点会成为COR的参数:第一种情况是,整个b+树只剩下根节点了,其他数据都删完了,那么这时候如果根节点中的数据也被删完了,这棵树就没有了,直接释放根节点对应的页即可。另一种情况,参考下图的过程:

    我们先删除了31所在的叶子节点,然后会对这个叶子节点调用COR函数,这时候30所在的节点就空了,就会继续递归调用COR,把两个中间节点合并,合并的同时,根节点的唯一一个元素也被删除了,即小于了minsize,此时就要对根节点调用COR函数,这边是需要调用Ajust函数的另一种情况,此时根节点是COR的参数,但是b+树非空,我们要做的就是删除原来的根节点,并设置新的根节点。

  • 跳表

    知乎上一篇文章讲的很好 https://zhuanlan.zhihu.com/p/53975333?ivk_sa=1024320u

    In general, a level has half the keys of one below it

    插入一个新节点后,关于是否要把这个新节点提拔到上一层的索引中,通过抛硬币来决定。

    插入过程:

    1. 新节点和各层索引节点逐一比较,确定原链表的插入位置。O(logN)

    2. 把索引插入到原链表。O(1)

    3. 利用抛硬币的随机方式,决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币,结果为“负”则停止。O(logN)

      总体上,跳跃表插入操作的时间复杂度是O(logN),而这种数据结构所占空间是2N,既空间复杂度是 O(N)。

      删除过程:

    4. 自上而下,查找第一次出现节点的索引,并逐层找到每一层对应的节点。O(logN)

    5. 删除每一层查找到的节点,如果该层只剩下1个节点,删除整个一层(原链表除外)。O(logN)

      总体上,跳跃表删除操作的时间复杂度是O(logN)。