Build Your Own Database

Summary

If you were to build your own database today, not knowing that databases exist already, how would you do it? In this post, we'll explore how to build a key-value database from the ground up. A key-value database works more or less like objects in JavaScript—you can store values using a key and retrieve them later using that same key: $ db set 'hello' 'world'$ db get 'hello'world Let's find out how they work! The Humble FileDatabases were made to solve one problem:How do we store data persistently and then efficiently look it up later?The typical way to store any kind of data persistently in a computer is to use a file . When we want to store data, we add the key-value pair to the file:$ db set 1 "Lorem ipsum"$ db set 18 "dolor sit"db.txt001: Lorem ipsum001:Lorem ipsum018: dolor sit018:dolor sitWhen we want to look for a specific key, we iterate through the pairs to see if there's a matching key:$ db set 1 "Lorem ipsum"$ db set 18 "dolor sit"db.txt001: Lorem ipsum001:Lorem ipsum018: dolor sit018:dolor sitFor updates, we'll find the key and replace the value in-place:$ db set 1 "Lorem ipsum"$ db set 18 "dolor sit"db.txt001: Lorem ipsum001:Lorem ipsum018: dolor sit018:dolor sitAnd for deletes, we'll delete the record from the file:$ db set 1 "Lorem ipsum"$ db set 18 "dolor sit"db.txt001: Lorem ipsum001:Lorem ipsum018: dolor sit018:dolor sitEasy! We're done right?db.txt001: Lorem ipsum001:Lorem ipsum018: dolor sit018:dolor sit Mutable Updates This approach, simple as it is, doesn't actually work very well in practice. The problem lies with the way we're doing updates and deletes—they're wholly inefficient. To a computer, our file looks something like this—nothing more than a long sequence of bytes: 001:Lorem␣ipsum\n018:dolor␣sit\n005:adipiscing␣elit.\n014:Vestibulum␣varius\n002:vel␣mauris\n007:consectetur␣adipiscing␣elit.\n010:Vestibulum␣varius\n016:vel␣mauris\n003:consectetur␣adipiscing␣elit. When we go to update or delete a record, we're currently updating that record...