Writing a sqlite clone from scratch in C
Dormant Last read · last published · next check
Read 11 hours ago and current, but nothing has been published for 2 years.
This project is no longer under active development. But if you’d like to keep learning how to make your own SQLite clone from scratch, or one of many other projects like Docker, Redis, Git or BitTorrent, try CodeCrafters . CodeCrafters maintains a pretty comprehensive list of “Build your own X” tutorials including “Build your own Database”. Plus, if your company has a learning and development…
The next leg of our journey will be splitting internal nodes which are unable to accommodate new keys. Consider the example below: Example of splitting an internal In this example, we add the key “11” to the tree. This will cause our root to split. When splitting an internal node, we will have to do a few things in order to keep everything straight: Create a sibling node to store (n-1)/2 of the…
For the next step on our epic b-tree implementation journey, we’re going to handle fixing up the parent node after splitting a leaf. I’m going to use the following example as a reference: Example of updating internal node In this example, we add the key “3” to the tree. That causes the left leaf node to split. After the split we fix up the tree by doing the following: Update the first key in the…
We now support constructing a multi-level btree, but we’ve broken select statements in the process. Here’s a test case that inserts 15 rows and then tries to print them. + it 'prints all rows in a multi-level tree' do + script = [] + (1..15).each do |i| + script << "insert #{i} user#{i} person#{i}@example.com" + end + script << "select" + script << ".exit" + result = run_script(script) + +…
Last time we ended with an error inserting our 15th row: db > insert 15 user15 person15@example.com Need to implement searching an internal node First, replace the code stub with a new function call. if (get_node_type(root_node) == NODE_LEAF) { return leaf_node_find(table, root_page_num, key); } else { - printf("Need to implement searching an internal node\n"); - exit(EXIT_FAILURE); + return…
Our B-Tree doesn’t feel like much of a tree with only one node. To fix that, we need some code to split a leaf node in twain. And after that, we need to create an internal node to serve as a parent for the two leaf nodes. Basically our goal for this article is to go from this: one-node btree to this: two-level btree First things first, let’s remove the error handling for a full leaf node: void…
Last time we noted that we’re still storing keys in unsorted order. We’re going to fix that problem, plus detect and reject duplicate keys. Right now, our execute_insert() function always chooses to insert at the end of the table. Instead, we should search the table for the correct place to insert, then insert there. If the key already exists there, return an error. ExecuteResult…
We’re changing the format of our table from an unsorted array of rows to a B-Tree. This is a pretty big change that is going to take multiple articles to implement. By the end of this article, we’ll define the layout of a leaf node and support inserting key/value pairs into a single-node tree. But first, let’s recap the reasons for switching to a tree structure. Alternative Table Formats With the…
The B-Tree is the data structure SQLite uses to represent both tables and indexes, so it’s a pretty central idea. This article will just introduce the data structure, so it won’t have any code. Why is a tree a good data structure for a database? Searching for a particular value is fast (logarithmic time) Inserting / deleting a value you’ve already found is fast (constant-ish time to rebalance)…
This should be a shorter part than the last one. We’re just going to refactor a bit to make it easier to start the B-Tree implementation. We’re going to add a Cursor object which represents a location in the table. Things you might want to do with cursors: Create a cursor at the beginning of the table Create a cursor at the end of the table Access the row the cursor is pointing to Advance the…
