MongoDB uses B-Trees for their indexing, which is great unless you have a specific need for anything else. In this case, I need to use AVL trees to keep a sorted list of documents based on a key within the documents (think keeping a sorted list) as the insertion, deletion, and searching should stay within O(log n) time. Does anybody have any idea how this can be done?
Hi @Alex_Mac,
Welcome to MongoDB Community.
Why wouldn’t indexing the relevant fields that you use for predicates will not work for you, if thy ar the only ones which gets projected those can be considered covered queries and therefore utelize only index.
Perhaps if you can share more on your data design and expected queries we might help you with your design better.
Best regards,
Pavel
Hi @Pavel_Duchovny,
Thank you for your response. In my current design, I am crudely clustering objects based on a similarity score. In memory, I am creating an AVL tree where my key (or sorted value) is this similarity score and the value is an _id.
For MongoDB, I am considering two possibilities:
- Is it possible to store such an AVL tree in MongoDB so that I do not have to reconstruct the tree each time?
- Instead of storing such a tree in memory (I am worried about scaling issues), is it possible to work directly on an AVL data structure on MongoDB as opposed to storing a structure in memory?
Using an AVL tree, for me, can guarantee sublinear performance in queries (insert, delete, and search).
Edit: Also, a key part of the AVL tree is the ability to view the parents and children of a node. AVL trees (when the key is the similarity) guarantees that the parents and children are closely related.
Thank you in advance,
Alex
Perhaps you can module your objects to best match your access pattern.
We do have several tutorials on saving tree data
See if any of those help you
Thanks