本实验我只完成2.1和2.2 2.3不会写,算了.

实验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

这一个部分我们需要结合之前的BufferPoolManager来完善哈希表的增删改查的操作.(一会儿我手画一下哈希表的结构)

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 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

隐藏