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
/
lql-parser
parser for my database project
And before I forget, this is the repo I've ripped most of the btree from >
Top comments (0)