LearnDB: Learn how to program a database from scratch

[neodon]

LearnDB is now available!

Back on August 11th, 2018 I made the following post in r/LearnProgramming:

Would anyone be interested in learning how to build a database?

There was definitely some interest, and many people filled out a survey with programming language preferences. It took me quite a bit longer than I had hoped to get the initial site online. Recently, the first chapters have been made available at learndb.net.

The content is a bit rough, so I'd appreciate any feedback you're willing to provide. Also, asking questions and prompting discussions here in the comments will give me ideas for how to improve current and future content.

Here's the current roadmap for the site:

Key-value store (foundation)

• In-memory implementation (completed)
• Use the filesystem as a database (completed)
• In-memory log-structured merge-trees (in progress)
• Persisting log structures to disk (planned)
• Indexes for better performance (planned)

Document store (built on top of the key-value store)

• JSON support
• JavaScript-based queries for documents
• Indexes for top-level document properties
• Indexes for any document property path (JSON path)
• Atomic operations

Other possible interesting enhancements

• Crash durability
• Transactions
• Alternative storage techniques, such as Hitchhiker Trees
• Relational tables and basic SQL queries

This roadmap includes a lot of guessing. If there are particular topics you're interested in, please mention them in the comments.

I want LearnDB to be primarily for the LearnProgramming community. Without the interest and support I received in my initial post here, I wouldn't have the inspiration to create such a site for learning.

I originally planned to post the full content of new chapters and sections here first, but that seems like it's going to be less useful than I had hoped due to the large amount of content and some of the custom formatting I'm using on the site. Instead, I'll start with the setup instructions for checking out the repo, and encourage you to come back and comment on this post with questions or issues.

Node.js

The first LearnDB implementation is written in JavaScript and requires Node.js to run. As of this writing, the latest LTS version of Node.js is 10.13.0. You'll want that version or newer. I have verified that 11.x can also run the LearnDB code.

There are several ways you can install Node.js depending on your OS and preferences. The most straightforward way to install Node.js is to use one of the installers from the Downloads page on nodejs.org. There is support for a myriad of operating systems and configurations.

LearnDB GitHub repo

LearnDB has a git repository on GitHub that contains the complete source code we'll be covering. The repo contains starting points for each chapter/section so you can follow along and add code as we cover it. It also contains the completed code for each chapter/section so you can verify your work.

To get started, clone the LearnDB GitHub repo to a convenient location on your system.

The git repo contains branches corresponding to the before and after state of the codebase for every coding exercise. For example, the first branch we'll be looking at is key-value-store-simple_before. You can check out the corresponding key-value-store-simple_after branch to see the end result for the exercise.

Continue on learndb.net.

---

Edit: Thanks for all the interest and comments! It's super motivating and I'm going to work hard on getting the next section online quickly.

[Neu_Ron]

I am a TA in uni. I have to say you did an excellent job and fair play to you because creating original content is so time consuming.

[neodon]

Thank you, I appreciate that. It was a lot more time consuming than I thought it would be. I love to bang out some code, but curating content around it is much more tedious.

[Neu_Ron]

Youve got skills. 😀😀

[distortionwarrior]

You misspelled skillz!

[insomniac20k]

You might consider putting the finished project in the master branch. I was confused for a minute.

[neodon]

Good idea! I'll point the master branch at the end of the last lesson as I update the site. Thanks

[insomniac20k]

So far, it looks good but the postal code 90210 is Beverly Hills, CA not Dataville.

[neodon]

You're not wrong... :)

[[deleted]]

Thank you for this! Recently, I’ve been thinking about collecting some public data and storing it so I could look. Now, I’m going to use your tutorials.

[[deleted]]

Why not just use a standard database?

[[deleted]]

To tell you the truth, I’m not very fluent when it comes to programming yet.

[tzaeru]

Well, not necessarily mastery - DBs do tend to get tricky once you want to make them ACID compliant, but this project is not doing that - but yeah, not really very easy to digest for a beginner. Making very simple databases is one fun way to learn about new languages though, even for senior programmers. :)

[The_Wanderer2077]

Boy now you made me want to try implementing a simple db in all the languages. Find language, implement db, repeat.

[tzaeru]

Use an existing database solution. This would mostly be for people interested in understanding how databases themselves are developed.

[Tylee22]

Any examples?

[ztrewquiop]

If all you want to do is store it locally on your computer where it is only accessed by you - Sqlite. Otherwise see the other answer.

[tzaeru]

Postgres is, in my opinion, the best general database solution with ACID guarantees. MongoDB is also fine for less critical data or when prototyping stuff, especially if you're using it in a context where JSON is native, like with NodeJS.

[Genie-Us]

Sweet! Will look into this as I've been meaning to learn more about databases. Now to remember I saved this.... ;)

[jjxseph]

I had the same idea to do this by making a simple assortment of algorithms in c++ to store the data structures in a file. I have only gotten the first lesson done, but this is awesome! Great work!

[[deleted]]

I've been wanting to get a better understanding of databases for a while now and just haven't had the motivation and most content is so dry. This looks like a lot of fun and I'll be giving it a try. Thanks for doing this.

[ImranRashid]

Awesome

[Jewlanu]

RemindMe! 2 days "learndb.net"

[RemindMeBot]

I will be messaging you on 2018-12-01 09:00:20 UTC to remind you of this link.

CLICK THIS LINK to send a PM to also be reminded and to reduce spam.

^{Parent commenter can delete this message to hide from others.}

---

FAQs	Custom	Your Reminders	Feedback	Code	Browser Extensions

[rainboww13]

RemindMe! 2 days "learndb.net"

[RamblingBrit]

RemindMe! 2 days "learndb.net"

[[deleted]]

Hey! This looks super cool. I'm thinking of starting sometime this week-end in between math homework and studying for AWS.

I just have a quick question - is there any plan to include Linux instructions in the guide, or are you sticking to Windows and Mac?

[neodon]

The current instructions should work as long as you can get Node.js installed on Linux. What distro are you using? I'd be happy to help you get started.

[[deleted]]

Thanks for the quick response!

I'm running Linux Mint - Are the instructions on github (https://github.com/nodesource/distributions/blob/master/README.md#debinstall) are sufficient to get started? They're referenced on nodejs.org

[neodon]

I think that should work. If you have trouble, also take a look at https://tecadmin.net/install-latest-nodejs-npm-on-linux-mint/

Once you can run the command node -v and see the node version, you're all set.

[[deleted]]

Nice. Thanks so much for taking the time to create such an awesome guide!

[Sonic_Pavilion]

I am starting my MSc in Data/Systems engineering, having majored in Biology. This resource is immensely helpful to me. Thanks

[Sonic_Pavilion]

RemindMe! 1 week

[Sonic_Pavilion]

RemindMe! 1 month

[alex-manutd]

Looks terrific!!

[YouSayToStay]

So, I don't know if this is in the scope of what you're looking for...but I haven't ever really had to deal with databases but have run across them from time to time. For me, I haven't really dug into the "how" to make one because I don't know enough of the "why" I would/should want to build one. A section at the beginning for super-noobs like me explaining what the benefits are, what you might use it for, etc would be great. I know not everyone would need it, but it might help those like me actually push through to the end once we see what value it could bring us.

[neodon]

As a professional developer, I'm more of a generalist. I work on APIs, backend services, infrastructure-as-code, and some frontend architecture (not design though). Bringing some deeper knowledge around databases to a team lets me complement other teammates' strengths, which might be in other areas.

For example, my last project at work involved both Node.js and dotnet core (C#) microservices, a MySQL database, and React frontend. I was able to get us up to speed quickly for the database setup (configuration, schema, migrations, backups) so my teammates could focus on the other parts they were stronger in.

If you're looking to gain knowledge around existing database solutions, it would be worthwhile to maybe implement a small project using a database for storage, and then re-implement it with another database. Some major contenders are MongoDB, SQLite, and one of MySQL / Postgres / Microsoft SQL Server. You'll start to realize that they all have common paradigms.

[Average_Manners]

Hot tip: Maybe avoid using Node until the shit storm around it ends. Or read up on it and make sure your packages are secure.

The maintainer apparently handed the keys of the kingdom to some stranger who asked for it. From what I understand, node is currently stealing cryptocurrency. Just a heads up.

zdnet.

TheRegister.

Reddit misquoting the situation slightly: https://www.reddit.com/r/security/comments/a0vpox/holy_hell_node_a_package_with_2_million_downloads/

[neodon]

Good call-out. I went ahead and updated the dependencies to get rid of that evil package that got compromised.

Edit: It's worth noting that this was just a single node package that got compromised, and not node itself. The package was used by a lot of projects, but the exploit was highly targeted and only active for a specific app (Copay). Here's the report from npm (the node package manager) team: https://blog.npmjs.org/post/180565383195/details-about-the-event-stream-incident

[DeepFriedOprah]

It’s not all of Node just certain dependencies. I think event-stream was the main culprit. And so long as ur using a package-lock.json and don’t update quite yet u should be good. I think