[Storage Engine] B+ Tree Implantation

Refer to the parent issue for more details

If no body wants to work on this I can take it up

i would love to, think this is really interesting. But i would need time to checkout #290 conversations aswell as getting the structure into my head

okay checked out the conversations and the current development plan. For the implementation of a structure like that, i would start with writing the following constrains:

fixed key datatyp since the b+ tree uses comparators to search and sort data (for example string or chars could get sorted lexiographical, int numerical et cetera) in the leafs guess its firstly more easy to keep the tree more deterministic.
i would try to write a minimal implementation with strong invariant testing. since i guess the most bugs will come up at splitting

Since i didnt really contribute anything till now idk if u let me but i would love to get a chance at this!!

So as it was given in issue #290, the main things that are supposed to be done by the B+ tree are to implement:

Search
Insert
Delete
Splitting
Leaf linking

My proposed plan is the following:

Assumptions:

Key-value database (not dealing with records, or a B+ tree for every index of a record, etc.)

Here we also need to agree upon what a key can be, since in #290 it is specified that we are having variable key lengths.

So here I assume a key as the string form of an object, as it is in general key-value databases.

Going with this, I think it is not possible to have range queries or utilise the leaf links.

Coming to the format for values, we can store their raw binary format data.

i think its safe to use pickle format for values

We can then use the disk manager API calls to access nodes of the tree, following serialisation or deserialisation, and proceed with search, insertion, or deletion operations.

Other responsibilities could include updating the metadata for keeping track of holes (empty pages).

an extra responsibility on which i would ask for everybodys view is the operation of bulk loading
does this project aim to cover that as part of the database??

If this approach looks reasonable, I would be happy to work on parts of the B+ tree implementation. I am also open to any input or corrections regarding the above approach.

So as it was given in issue #290, the main things that are supposed to be done by the B+ tree are to implement:

Search

Insert

Delete

Splitting

Leaf linking

My proposed plan is the following:

Assumptions:

Key-value database (not dealing with records, or a B+ tree for every index of a record, etc.)

Here we also need to agree upon what a key can be, since in #290 it is specified that we are having variable key lengths.

So here I assume a key as the string form of an object, as it is in general key-value databases.

Going with this, I think it is not possible to have range queries or utilise the leaf links.

Coming to the format for values, we can store their raw binary format data.

i think its safe to use pickle format for values

We can then use the disk manager API calls to access nodes of the tree, following serialisation or deserialisation, and proceed with search, insertion, or deletion operations.

Other responsibilities could include updating the metadata for keeping track of holes (empty pages).

an extra responsibility on which i would ask for everybodys view is the operation of bulk loading does this project aim to cover that as part of the database??

If this approach looks reasonable, I would be happy to work on parts of the B+ tree implementation. I am also open to any input or corrections regarding the above approach.

I think we should be careful with some of these assumptions.

For B+ tree itself, I'd prefer keeping keys as raw bytes rather than converting everything to strings. the python object to bytes conversion can be handled by a key/value codec layer I recommended in #290. so the tree doesn't need to know what the original key type was.

Also, leaf linking is actually useful for range queries. Once we find the first matching leaf, we can follow the leaf links instead of traversing the tree again and again for every key.

I 'd keep the initial B+ tree implementation focused on search, insert, delete, splitting, merging/tree rebalancing, and leaf linking.

For bulk loading I thing we can leave it out for now and add it later if we actually need it. I would like to ask the others opinion on this though.

okay checked out the conversations and the current development plan. For the implementation of a structure like that, i would start with writing the following constrains:

fixed key datatyp since the b+ tree uses comparators to search and sort data (for example string or chars could get sorted lexiographical, int numerical et cetera) in the leafs guess its firstly more easy to keep the tree more deterministic.

i would try to write a minimal implementation with strong invariant testing. since i guess the most bugs will come up at splitting

Since i didnt really contribute anything till now idk if u let me but i would love to get a chance at this!!

I think the constraints/invariants approach makes a lot of sense here , especially since splitting probably going to be one of the trickier parts to ger right.
I'm not sure too sure I'd settle on a fixed key datatype yet though.
I also agree that keeping initial implementation minimal and putting more effort into invaraiant testing would be a good approach.

@indrakantisaidharahas

Well fair enough about the key datatype. I do think for a first implementation it makes a lot of sence since the key must represent a comparator. later on when the tree works with one value datatype for example int you can add this. i just think its minimizes bugs in the first generation.

@indrakantisaidharahas well someone has to decide who does this or we arrange ourselfs do the pairprogramming or someone does the first initial design and someone else the optimisations

@sowashieristjaschoninteressant

@sowashieristjaschoninteressant, i am happy to work on some parts of the initial b+ tree implementation as well, not only the optimisations. i might be a bit busy this week, so you guys can go ahead with the initial design and implementation, and i can take up some parts along the way and coordinate with you, if that is okay with you guys. if there is anything i can take up this weekend or next week, please let me know.

okay sure sound like a plan!

@sowashieristjaschoninteressant

@sowashieristjaschoninteressant and @indrakantisaidharahas thanks for taking the initiative. If you guys want you both can work together but since @sowashieristjaschoninteressant was the first to respond he will be given priority by me.
You can open PRs when you feel your implementation is ready.

I also agree that a codec layer might be needed but I don't think it should be included in the B+ tree. I think a good first implementation would be something that can insert, delete, search for items in bytes and then return the raw bytes which will be processed by codec layer or anything else we plan to add in the future.

Hi, after looking at the conversation in #290, I am keen to see how I can contribute in this implementation of the B+ tree.

I can probably do some research on how the codec layer should be implemented before writing a rough idea here.

Hi, after looking at the conversation in #290, I am keen to see how I can contribute in this implementation of the B+ tree.

I can probably do some research on how the codec layer should be implemented before writing a rough idea here.

Hey if you wanna discuss the codec you can do so in the parent issue. I will open a new sub-issue related to the codec implementation. I don't now sure if we need to wait for B tree to implement codec and so on.

okay i opened a draft pr if pple are interested on the continuation. there is still some work i have to do the algorithms are quite complicated but i managed to write a first version of the splitting algo. if someone wants to do delete or get ur welcome. i need to refactor a bit anyway now

I have a query regarding the B+ tree implementation.

The code in the pull request looks good to me, but while reading it I had a doubt. How do we map the indexes in the B+ tree classes to the pointers we have in the disk pages? Will we face any conflict there, and if yes, do we use a translation table for it?

For example, here the traversal moves through object references:

internalNode: _InternalNode = node
nodeIndex = self._find_position(internalNode._keys, key)
node = internalNode._children[nodeIndex]

I have a query regarding the B+ tree implementation.

The code in the pull request looks good to me, but while reading it I had a doubt. How do we map the indexes in the B+ tree classes to the pointers we have in the disk pages? Will we face any conflict there, and if yes, do we use a translation table for it?

For example, here the traversal moves through object references:
internalNode: _InternalNode = node
nodeIndex = self._find_position(internalNode._keys, key)
node = internalNode._children[nodeIndex]

Good question but I request you to talk about the PRs implementation in the PR itself

@sowashieristjaschoninteressant

Why does #338 not mention this?

I think @sowashieristjaschoninteressant is kinda assigned so maybe assign it to him, and maybe more?

Navigation Menu

Repository navigation

[Storage Engine] B+ Tree Implantation #333

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

[Storage Engine] B+ Tree Implantation #333

Description

Activity

VihaanReddyM commented on Oct 5, 2026

sowashieristjaschoninteressant commented on Oct 5, 2026

sowashieristjaschoninteressant commented on Oct 5, 2026

indrakantisaidharahas commented on Oct 5, 2026

mohammedFawzy0111 commented on Oct 5, 2026

mohammedFawzy0111 commented on Oct 5, 2026

sowashieristjaschoninteressant commented on Oct 5, 2026

indrakantisaidharahas commented on Oct 5, 2026

sowashieristjaschoninteressant commented on Oct 5, 2026

VihaanReddyM commented on Oct 6, 2026

VihaanReddyM commented on Oct 6, 2026

yongggquannn commented on Oct 6, 2026

VihaanReddyM commented on Oct 7, 2026

sowashieristjaschoninteressant commented on Oct 7, 2026

indrakantisaidharahas commented on Oct 7, 2026

VihaanReddyM commented on Oct 8, 2026

mattsva commented on Oct 8, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions