Creating a database from scratch with Node.js - Day 12

Hello folks!

Here am I, talking about my database study project again

Today I had the plan to implement the indexing algorithm, turns out I started it but it will take me more time.

Here is what I did today

Fixed a bug in LQL parser

I had a bug where the parser would spit out two statements instead of one

Pretty sure this is meant to be the Nearley feature that allows you to parse ambiguous language, but for now, I made the parser always return a single statement object.

Split the database tables into files

This project was using a single file to represent the entire database, now each table has its own file with "ldbt" extension (which is still just a JSON).

in this file, I will only record the actual rows, the table information like which row is nullable and which row is a primary key, etc will stay in the main database file.

This will be useful for three reasons:

• The database will not load tables that are not being used, and will therefore save memory
• Once I create an index, and I have that situation I mentioned where the index has all the information needed to perform a query, loading the database file won't even be necessary
• This is the first step to support partition

Started implementing BTrees indexes

I have just began doing this, for now, my BTree can only insert values and find them, it's not balancing itself yet, and it doesn't support deleting

This is the test file I've written so far:

and this is the output:

the parent attribute is always null for now, it's purposely done this way, so I can log the entire thing without it becoming an infinite loop of references

I've read a lot of resources, but this is the one I've liked the most, so if anyone wants to learn how to create a btree, just take a look at this repository >

It has no tutorial, but the code is very clean and easy to understand.

Tomorrow I will keep working on the BTree. I will try to implement deletion and rebalancing.

If I can do this quickly, I will finish implementing indexing

If anyone wants to take a look at the code or play around with the database, these are the repositories for the project:

LuisDB:

Note: the version I've used in this particular post is in a branch called index

LQL parser: