OceanBase 数据库大赛：唯一索引思路分析

程序员小王

发布于 2021-11-18 14:16:26

9540

发布于 2021-11-18 14:16:26

文章被收录于专栏：架构说

PICK OF THE WEEK

一、最少知识（可以看视频）

lectures-on-dbms-implementation

https://oceanbase-partner.github.io/lectures-on-dbms-implementation/lecture-2
第2章数据库的存储结构

2019CMU数据库导论(intro to database systems fall 2019) - https://www.bilibili.com/video/BV1U7411K7TM?p=8 - https://www.bilibili.com/video/BV1U7411K7TM?p=3

CMU15 445/645课程-Tree Based Indexes笔记
CMU 15-445 Fall 2020 Labs 实现笔记
https://cs.carleton.edu/faculty/awb/cs334/s21/projects/project1.html

OceanBase 数据库大赛

OceanBase 数据库大赛（第五期直播回放） https://www.bilibili.com/video/BV1u34y1m7G5
OceanBase 数据库大赛（第四期直播回放） https://www.bilibili.com/video/BV1wg411F7zm
OceanBase 数据库大赛（第三期直播回放） https://www.bilibili.com/video/BV1GP4y1h7tZ
OceanBase 数据库大赛（第二期直播回放） https://www.bilibili.com/video/BV1pq4y1f7BT （这个一定要看）

b+ tree的查找逻辑：

提示：这里为什么一定区分叶子节点呢 https://en.wikipedia.org/wiki/B%2B_tree

二、思路分析

如果证明这个这个索引是普通索引还是唯一索引呢？TableMeta 插入时候如何判断重复呢？
测试对比发现：插入一个记录不提示节点重复，更新索引：提示节点重复，他们之间差别就不同的page？对比插入逻辑和更新逻辑
有人知道 slot_num是干啥用的不？ https://oceanbase-partner.github.io/lectures-on-dbms-implementation/lecture-2
b+ 查找和插入算法描述是什么？

三、代码实现

##      插入逻辑 和索引的关系

case SCF_INSERT:

make_record(value_num, values, record_data);

Operation::Type::INSERT



index->insert_entry(record, &rid);


  

## 更新和索引的关系
## 更新和索引的关系

case SCF_UPDATE:
  
  RC Table::commit_update(T
                          
                          
  Record oldrecord;
  rc = record_handler_->get_record(&rid, &oldrecord);
  
  
  RC Table::scan_record_by_index(T
  
      RC Trx::commit() {
  
    RID rid;
      rid.page_num = operation.page_num();
      rid.slot_num = operation.slot_num();
  
  
RC Table::commit_insert(Trx *trx, const RID &rid)


rc = index->insert_entry(oldrecord.data, &oldrecord.rid);
/**
   * 获取指定文件中标识符为rid的记录内容到rec指向的记录结构中
   * @param rid
   * @param rec
   * @return
   */
  RC get_record(const RID *rid, Record *rec);

                                 
## 查找和索引的关系

case SCF_SELECT:

RC SelectExeNode::execute(TupleSet &tuple_set) 

return scan_record(trx, filter, limit, (void *)&adapter, scan_record_reader_adapter);
                   
IndexScanner *Table::find_index_for_scan(const DefaultConditionFilter &filter)

RC Table::scan_record_by_index(
  
  RC BplusTreeHandler::insert_entry(const char *pkey, const RID *rid) {
  
  
  
## 插入一行记录 case SCF_INSERT:

Table::insert_record(Trx *trx, int value_num, const Value *values) 

Record

RC BplusTreeHandler::insert_entry(const char *pkey, const RID *rid) {

  class BplusTreeIndex : public Index {
    
    RC BplusTreeHandler::insert_entry(const char *pkey, const RID *rid) 
    
    RC BplusTreeScanner::open
    
   ## 干啥呢
    int CmpKey(AttrType attr_type, int attr_length, const char *pdata, const char *pkey)
{
  int result = CompareKey(pdata, pkey, attr_type, attr_length);
  if (0 != result) {
    return result;
  }
  RID *rid1 = (RID *) (pdata + attr_length);
  RID *rid2 = (RID *) (pkey + attr_length);
  return CmpRid(rid1, rid2);
}
    
    RC BplusTreeHandler::insert_into_leaf(PageNum leaf_page, const char *pkey, const RID *rid)
    
    参考：更新逻辑
   rc = index->insert_entry(oldrecord.data, &oldrecord.rid);
f(rc ==RC::RECORD_DUPLICATE_KEY)
      {
        rc =RC::SUCCESS;
      }    
    
    RC BplusTreeScanner::next_entry(RID *rid) {

四、调试

## 查找叶子节点
breakpoint set --file bplus_tree.cpp --line 284
breakpoint set --file bplus_tree.cpp --line 818
breakpoint set --file default_storage_stage.cpp --line 239



insert into t values(1,11, "a","2021-3-1",1.1);

update t set birthday='2021-3-11'  where   birthday='2021-3-11';

unique: result file difference(`-` is yours and `+` is base)
 1. UNIQUE TEST
 CREATE UNIQUE INDEX INDEX_ID ON UNIQUE_TABLE(ID);
 SUCCESS
 INSERT INTO UNIQUE_TABLE VALUES (2,1,1);
 SUCCESS
 CREATE UNIQUE INDEX INDEX_ID ON UNIQUE_TABLE(ID);
 FAILURE
 INSERT INTO UNIQUE_TABLE VALUES (3,2,1);
 SUCCESS
 INSERT INTO UNIQUE_TABLE VALUES (1,2,1);
-SUCCESS
+FAILURE