search

XiangpengHao / congee

Concurrent ART (adaptive radix tree)
MIT License
130 stars 8 forks source link

Some thoughts on generic keys #10

Open XiangpengHao opened 1 year ago

XiangpengHao commented 1 year ago

Current generic key support in Congee is broken: every key type is stored as usize and compared as usize. The ordering of the original generic key is ignored. ART is a radix tree and implicitly assumes keys to be strings. It supports integer numbers because it happens to have a meaningful byte-order (depending on the endian).

Therefore only two types of keys are meaningful to Congee: string and integer numbers. In fact, production database may only support string keys as the index (e.g., BigTable). In the future, Congee will only support string. Support for integer numbers will be a syntax sugar.

MirroredLens commented 3 weeks ago

Curious to know if this may happen. Would be great to support arbitrary size keys.

With experience building congee, I just wanted to know if turning blart (https://github.com/declanvk/blart) into a concurrent version would be easier than modifying congee to support arbitrary size keys or vice versa.

Any insights will be helpful, thanks.

XiangpengHao commented 3 weeks ago

Hi @MirroredLens , thank you for the interests in Congee. I'm currently not actively working on congee. I think it adding var len key support to congee should be straightforward. I'm not familiar with blart though.

MirroredLens commented 3 weeks ago

Hello @XiangpengHao, sad to hear that you're no longer actively working on congee. It's such a high potential data structure imo, and you've made such an impressive version of a concurrent art tree that rivals concurrent hashmaps and beats out other concurrent trees!

Can you give me any advice on how to add variable length keys for congee? Such that the optimizations may still hold for larger keys.

Thanks.

XiangpengHao commented 2 weeks ago

Sorry for the late reply! To support variable length key, we need to store the string keys in a separate buffer and manage the string spaces there. In the get operation, once we reached the leaf node of the tree, we need to load the full key and compare if they are the same. The implementation should be straightforward, but getting it correct and efficient can be quite challenging.

MirroredLens commented 2 weeks ago

Sounds hard to keep the optimizations intact.

Just curious if you might implement this someday or if it's not within the need or scope of the project. Feel free to close the issue if not.

Thanks.