查看原文
其他

实现一个简单的Database6(译文)

花家舍 GreatSQL社区 2024-07-08

* GreatSQL使

前文回顾


译注:cstack在github维护了一个简单的、类似sqlite的数据库实现,通过这个简单的项目,可以很好的理解数据库是如何运行的。本文是第六篇,主要是实现游标抽象

Part 6 游标抽象

跟上一节相比,这一节篇幅相对要简短的多。我们只是稍微重构一下,这样就可以让开始实现B-tree更简单一些。

在代码中新添加一个Cursor对象,它用来代表表中的一个位置(location)。

你可能希望对游标执行的操作:

  • 在表开头时创建一个游标
  • 在表结尾时创建一个游标
  • 访问游标指向的行
  • 将游标移动到下一行

这就是我们将要实现的游标的一些行为。然后,我们还想做到:

  • 删除游标指向的一行数据
  • 修改游标指向的一行数据
  • 使用给定的ID搜索一张表,并创建一个游标指向这个ID所在的行

译注:这里简单介绍一下游标,Cursor原本就有箭头、光标的意思,用来指示事物以示关注。游标是数据的一种访问机制,一种处理数据的方法,例如查询返回的结果是一行或者多行的结果集(这已经是SQL被处理后的结果集),我们需要对结果集进行查询,sql语句就不管用了,因为这已经是返回的结果集了,这个时候就需要用游标来遍历这个返回的结果集了。可以理解游标是一个指向Row的指针,访问一行后,游标就会指向下一行。例如 fetchone()fetchall() 等函数就是通过游标来访问结果集的,返回具体一行或者多行的数据。下面是游标图示:

不磨叽了,下面就是Cursor类型结构:

+typedef struct {
+  Table* table;
+  uint32_t row_num;
+  bool end_of_table;  // Indicates a position one past the last element
+} Cursor;

根据现在我们的表数据结构,只需要行号即可识别表中的位置。

游标所属的表,游标对它还有一个引用(所以我们的游标函数还可以仅仅把游标作为参数)。

最后,它还有一个boolean类型的属性叫做 end_of_table 。这样我们就可以用来表示表结尾之后的位置(在这里我们可能会插入一个新行)。

table_start()table_end() 创建一个新的游标:

+Cursor* table_start(Table* table) {
+  Cursor* cursor = malloc(sizeof(Cursor));
+  cursor->table = table;
+  cursor->row_num = 0;
+  cursor->end_of_table = (table->num_rows == 0);
+
+  return cursor;
+}
+
+Cursor* table_end(Table* table) {
+  Cursor* cursor = malloc(sizeof(Cursor));
+  cursor->table = table;
+  cursor->row_num = table->num_rows;
+  cursor->end_of_table = true;
+
+  return cursor;
+}

我们的 row_slot() 函数要变成 cursor_value() 了,它返回一个指针类型,指向游标描述的位置:

-void* row_slot(Table* table, uint32_t row_num) {
+void* cursor_value(Cursor* cursor) {
+  uint32_t row_num = cursor->row_num;
   uint32_t page_num = row_num / ROWS_PER_PAGE;
-  void* page = get_page(table->pager, page_num);
+  void* page = get_page(cursor->table->pager, page_num);
   uint32_t row_offset = row_num % ROWS_PER_PAGE;
   uint32_t byte_offset = row_offset * ROW_SIZE;
   return page + byte_offset;
 }

在我们当前的表结构中推进游标就像让行号递增一样简单。这在B-tree中会有一点小复杂。

+void cursor_advance(Cursor* cursor) {
+  cursor->row_num += 1;
+  if (cursor->row_num >= cursor->table->num_rows) {
+    cursor->end_of_table = true;
+  }
+}  

最后我们就能改变我们的“虚拟机”方法来使用游标抽象了。当插入一行数据时,我们在表结尾打开一个游标,写入这个游标的位置,然后关闭游标。

Row* row_to_insert = &(statement->row_to_insert);
+  Cursor* cursor = table_end(table);

-  serialize_row(row_to_insert, row_slot(table, table->num_rows));
+  serialize_row(row_to_insert, cursor_value(cursor));
table->num_rows += 1;

+  free(cursor);
+
return EXECUTE_SUCCESS;
}

当查询表中的所有行时,我们在表的开头打开一个游标,打印行数据,然后推进游标到下一行,重复这个过程直到表的结尾。

 ExecuteResult execute_select(Statement* statement, Table* table) {
+  Cursor* cursor = table_start(table);
+
   Row row;
-  for (uint32_t i = 0; i < table->num_rows; i++) {
-    deserialize_row(row_slot(table, i), &row);
+  while (!(cursor->end_of_table)) {
+    deserialize_row(cursor_value(cursor), &row);
     print_row(&row);
+    cursor_advance(cursor);
   }
+
+  free(cursor);
+
   return EXECUTE_SUCCESS;
 }

好了,就是它!就像我说的,这是短小的重构,应该能够有助于我们把表的数据结构重写为B-tree。execute_select()execute_insert() 函数完全可以通过游标来与表交互,而对于表的存储方式不需要假设任何事情。

译注:在之前实现数据库的page组织方式的代码中,作者使用数组(array)来组织数据页page,主要是考虑快速实现存放数据,没有考虑性能优化。后面会使用B-tree来进行重构,而在此之前,先实现了游标。

这是于上一部分对比,代码的不同:

@@ -78,6 +78,13 @@ struct {
 } Table;

+typedef struct {
+  Table* table;
+  uint32_t row_num;
+  bool end_of_table; // Indicates a position one past the last element
+} Cursor;
+
 void print_row(Row* row) {
     printf("(%d, %s, %s)\n", row->id, row->username, row->email);
 }
@@ -126,12 +133,38 @@ void* get_page(Pager* pager, uint32_t page_num) {
     return pager->pages[page_num];
 }

-void* row_slot(Table* table, uint32_t row_num) {
-  uint32_t page_num = row_num / ROWS_PER_PAGE;
-  void *page = get_page(table->pager, page_num);
-  uint32_t row_offset = row_num % ROWS_PER_PAGE;
-  uint32_t byte_offset = row_offset * ROW_SIZE;
-  return page + byte_offset;
+Cursor* table_start(Table* table) {
+  Cursor* cursor = malloc(sizeof(Cursor));
+  cursor->table = table;
+  cursor->row_num = 0;
+  cursor->end_of_table = (table->num_rows == 0);
+
+  return cursor;
+}
+
+Cursor* table_end(Table* table) {
+  Cursor* cursor = malloc(sizeof(Cursor));
+  cursor->table = table;
+  cursor->row_num = table->num_rows;
+  cursor->end_of_table = true;
+
+  return cursor;
+}
+
+void* cursor_value(Cursor* cursor) {
+  uint32_t row_num = cursor->row_num;
+  uint32_t page_num = row_num / ROWS_PER_PAGE;
+  void *page = get_page(cursor->table->pager, page_num);
+  uint32_t row_offset = row_num % ROWS_PER_PAGE;
+  uint32_t byte_offset = row_offset * ROW_SIZE;
+  return page + byte_offset;
+}
+
+void cursor_advance(Cursor* cursor) {
+  cursor->row_num += 1;
+  if (cursor->row_num >= cursor->table->num_rows) {
+    cursor->end_of_table = true;
+  }
 }

 Pager* pager_open(const char* filename) {
@@ -327,19 +360,28 @@ ExecuteResult execute_insert(Statement* statement, Table* table) {
     }

   Row* row_to_insert = &(statement->row_to_insert);
+  Cursor* cursor = table_end(table);

-  serialize_row(row_to_insert, row_slot(table, table->num_rows));
+  serialize_row(row_to_insert, cursor_value(cursor));
   table->num_rows += 1;

+  free(cursor);
+
   return EXECUTE_SUCCESS;
 }

 ExecuteResult execute_select(Statement* statement, Table* table) {
+  Cursor* cursor = table_start(table);
+
   Row row;
-  for (uint32_t i = 0; i < table->num_rows; i++) {
-     deserialize_row(row_slot(table, i), &row);
+  while (!(cursor->end_of_table)) {
+     deserialize_row(cursor_value(cursor), &row);
      print_row(&row);
+     cursor_advance(cursor);
   }
+
+  free(cursor);
+
   return EXECUTE_SUCCESS;
 }

Enjoy GreatSQL :)



《零基础学习MySQL

B

https://www.bilibili.com/video/BV1Da411W7Va?spm_id_from=333.999.0.0&vd_source=ae1951b64ea7b9e6ba11f1d0bbcff0e4


文章推荐:



关于 GreatSQL

GreatSQL是由万里数据库维护的MySQL分支,专注于提升MGR可靠性及性能,支持InnoDB并行查询特性,是适用于金融级应用的MySQL分支版本。


GreatSQL社区官网: 
https://greatsql.cn/

Gitee: 
https://gitee.com/GreatSQL/GreatSQL

GitHub: 
https://github.com/GreatSQL/GreatSQL

 Bilibili

https://space.bilibili.com/1363850082/video



捉虫活动详情:https://greatsql.cn/thread-97-1-1.html

社区博客有奖征稿详情:https://greatsql.cn/thread-100-1-1.html

(对文章有疑问或者有独到见解都可以去社区官网提出或分享哦~)


&QQ

可扫码添加GreatSQL社区助手微信好友,送验证信息“加群”加入GreatSQL/MGR交流微信群,亦可直接扫码加入GreatSQL/MGR交流QQ群


QQ


想看更多技术好文,点个“在看”吧!

继续滑动看下一个
向上滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存