增加功能: 按照主键有序排列; 消除主键冲突
现在我们插入记录时依旧是在表的最后插入,因此数据记录是无序的。
在这一节中,我们要找到table中正确的位置去插入。如果这个位置已经有要插入的key,报错(说明主键已经存在)
因为记录需要按顺序存储,因此插入的时候可以使用二分查找。
Cursor* table_find(Table* table,uint32_t key){
void* root_node= get_page(table->pager,table->root_page_num);
// printf("%d", get_node_type(root_node));
if(get_node_type(root_node)==NODE_LEAF){
return leaf_node_find(table,table->root_page_num,key);
}
else{
printf("Internal Node\n");
exit(EXIT_FAILURE);
}
}
Cursor* leaf_node_find(Table* table,uint32_t page_num,uint32_t key){
void* node= get_page(table->pager,page_num);
uint32_t num_cells= *leaf_node_num_cells(node);
Cursor* cursor= malloc(sizeof(Cursor));
cursor->table=table;
cursor->page_num=page_num;
//cursor->cell_num ??
//Binary Search
// find key from [0,num_cells)
uint32_t left=0,right=num_cells;
while(left<right){
uint32_t mid=(left+right)/2;
uint32_t mid_key= *leaf_node_key(node,mid);
if(mid_key==key){
cursor->cell_num=mid;
return cursor;
}
if(key<mid_key){
right=mid;
}
else{
left=mid+1;
}
}
cursor->cell_num=left;
return cursor;
}
void leaf_node_insert(Cursor* cursor,uint32_t key,Row* value){
void* node= get_page(cursor->table->pager,cursor->page_num);
uint32_t num_cell= *leaf_node_num_cells(node);
if(num_cell>LEAF_NODE_MAX_NUM){
printf("Need to implement splitting a leaf Node\n");
exit(EXIT_FAILURE);
}
if(cursor->cell_num<num_cell){
for(uint32_t i=num_cell;i>cursor->cell_num;i--){
memcpy(leaf_node_cell(node,i), leaf_node_cell(node,i-1),LEAF_NODE_CELL_SIZE);
}
}
*leaf_node_num_cells(node)+=1;
*leaf_node_key(node,cursor->cell_num)=key;
serialize_row(value, leaf_node_value(node,cursor->cell_num));
}
ExecuteResult execute_insert(Statement* statement,Table* table){
void* page= get_page(table->pager,table->root_page_num);
uint32_t num_cells= *leaf_node_num_cells(page);
if(num_cells>=LEAF_NODE_MAX_NUM){
return EXECUTE_TABLE_FULL;
}
Row *row=&(statement->row);
uint32_t key=row->id;
Cursor* cursor= table_find(table,key);
if(cursor->cell_num<num_cells){
uint32_t key_at_index=*leaf_node_key(page,cursor->cell_num);//得到要插入的位置的值
if(key==key_at_index){ //如果发现
return EXECUTE_DUPLICATE_KEY;
}
}
leaf_node_insert(cursor,row->id,row);//key没有重复,插入
return EXECUTE_SUCCESS;
}