增加功能： 按照主键有序排列； 消除主键冲突

一、概述

现在我们插入记录时依旧是在表的最后插入，因此数据记录是无序的。
在这一节中，我们要找到table中正确的位置去插入。如果这个位置已经有要插入的key，报错（说明主键已经存在）

因为记录需要按顺序存储，因此插入的时候可以使用二分查找。

二、代码实现

1. 在某table的根中插入key以及对应的value

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);}}

2. 进入到该node中，插入新的cell，需要先找到插入的位置（因为node中记录有序，二分查找）
   leaf_node_find

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;}

3. 执行插入操作

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;
}