Creating a database from scratch with Node.js - Days 13-14

Hello folks!

Quick update on my database project

I finally did it, my database now (kinda) supports indexing!

hell yeah.

I will cover some of what I did in this post

Most of my btree implementation is a ripoff from the repository I've mentioned in my last post (will link it again at the end of this post)

the exception are:

• the search function, that actually retrieves me an array from my index based on a comparing function
• the conversion functions, that create a JSON from a btree and a btree from a JSON

Alright, so here is how it works

Creating an index

The statement for creating an index is:

create index [INDEX NAME] on [TABLE] [COLUMN]

This statement goes through the database and creates a binary tree from that column and saves it as a JSON with the specified name in the root folder of the database:

It's kinda convoluted, I know

Searching the index

Once you have the index created, every select statement you make will consider using the index instead of a full-table search

It will use the index whenever the index contains everything needed to solve the query (any columns the user asked for and any columns needed for the where statement)

There is only one problem with the way I'm currently doing the search in this tree, I am not considering the operation being tested by the where function so I am not locking the paths it would not make sense to search

I am not 100% sure, but about 95% sure, that this makes the big O for the search become O(n) instead of O(log n)

And I have the intention to fix this.

These are the times for the same searches without using the index

So, it is still faster, but I am pretty sure that locking the path the tree should not search will make it a lot faster

Things I will have to work on

• Fix search
• Inserting/Deleting/Changing values from index if a record changes in the database
• Support for multiple equal values
• Support for adding new columns in the index
• Drop index

Conclusion

Well, this is the part I've been most excited to reach since I've started the project

I know it is far from perfect (or even good) but I am proud of it

I will try to add all these things I said tomorrow, none of them seem to be super complicated.

BTW: I've been reading the book clean code and I am refactoring a lot of this project as I read it

I am some who is always telling people they should focus on readability and 3 chapters on this book and I realized I have a lot of room to improve

So yeah, all this refactoring I am doing now is slowing me down a bit, but should allow me to keep going fast in the long term :)

And that's it

If anyone wants to play around or read the code, the repository for the database and the parser are these >

ciochetta / learndb

Database project I've created for learning purposes

ciochetta / lql-parser

parser for my database project

And before I forget, this is the repo I've ripped most of the btree from >

QuotableWater7 / btree

A rebalancing binary tree for JS