DEV Community

loading...
Cover image for Creating a database from scratch with Node.js - Days 15-16

Creating a database from scratch with Node.js - Days 15-16

Luis Felipe Ciochetta
Brazilian software engineer, trying to document my studies and read nice articles on this platform.
・2 min read

Hello folks!

I am back with my DBMS project;

I was not posting about it in the last few days because I was in a hackathon, but now I can proceed with my studies.

Alright, first of all, I did not document the things I said I would, but I will get there eventually;

I have severely underestimated the time it would take to optimize the search algorithm and the time it would take to add the index maintenance to my insert/delete/update functions

so here is what I managed to do in the last two days:


Optimize the search algorithm

In my last post I've said this:

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)

Well, now the irrelevant paths are being locked, which means the search is no longer broken

To do this, I did something similar to the way I create the comparing function

I have a function that returns a function that says if the search should ignore a path based on the operator (==, <, > etc), the value being compared, the value for the current node, and the value for the next node

Something like this:

Alt Text

this alone took me hours to figure out and write test functions


Insert new values in the index

The other thing I've managed to do is to update my indexes as I add new values to my databases

Here is how it's working

I have just created a new table "users" with only one document:

Alt Text

And I have created an index for the name of the users:

Alt Text

Then, I have inserted a new user in the table:

Alt Text

And this is how the index looks now:

Alt Text

So yeah, it's working


Conclusion

I see now that I got a little too cocky in my last post saying I would solve all my index problems in one day

I kept reading the book clean code and I came to the conclusion I will have to do a big refactor on some of my functions, including the insert function I wrote today

So my next day of work will probably be spent only refactoring

And that's it, thank you for reading

If anyone wants to read the code or play around with the project, this is the repository for the database >

GitHub logo ciochetta / learndb

Database project I've created for learning purposes

and for the parser >

GitHub logo ciochetta / lql-parser

parser for my database project

Discussion (0)