Background: I am trying to implement a fully dynamic connectivity algorithm, based on this paper (https://dl.acm.org/doi/10.1145/502090.502095), using LMDB as the backend. Other implementations use an in-memory binary search tree. I am currently working on trying to implement an Euler Tour Forest using LMDB. Essentially, an Euler Tour of an unbalanced tree is obtained by doing a DFS and assigning an increasing index every time we visit a node (https://en.m.wikipedia.org/wiki/Euler_tour_technique). An Euler Tour Tree is simply a balanced tree containing the euler tour index as the key and a pointer to the node as the value, so I plan to store each Euler Tour Tree using an LMDB database.
Problem: I need an unlimited amount of sub-databases - my first thought was to use mdb_dbi_open, however, it seems like this doesn't scale well because a list of named sub-databases is stored in every transaction. In the talk about LMDB's functionality at CMU (https://www.youtube.com/watch?v=tEa5sAh-kVk) there is some reference to sub-databases, but from reading the code it seems like unnamed sub-databases are only used for sorted duplicate keys.
Am I correct in thinking that I'm going to need to add some new code to support unnamed sub-databases, or is there some way to do it that I'm not recognizing? And if I do need to change things, where should I start?
Ruben Soh
ruben.soh@rutgers.edu wrote:
Background: I am trying to implement a fully dynamic connectivity algorithm, based on this paper (https://dl.acm.org/doi/10.1145/502090.502095), using LMDB as the backend. Other implementations use an in-memory binary search tree. I am currently working on trying to implement an Euler Tour Forest using LMDB. Essentially, an Euler Tour of an unbalanced tree is obtained by doing a DFS and assigning an increasing index every time we visit a node (https://en.m.wikipedia.org/wiki/Euler_tour_technique). An Euler Tour Tree is simply a balanced tree containing the euler tour index as the key and a pointer to the node as the value, so I plan to store each Euler Tour Tree using an LMDB database.
Problem: I need an unlimited amount of sub-databases - my first thought was to use mdb_dbi_open, however, it seems like this doesn't scale well because a list of named sub-databases is stored in every transaction. In the talk about LMDB's functionality at CMU (https://www.youtube.com/watch?v=tEa5sAh-kVk) there is some reference to sub-databases, but from reading the code it seems like unnamed sub-databases are only used for sorted duplicate keys.
Am I correct in thinking that I'm going to need to add some new code to support unnamed sub-databases, or is there some way to do it that I'm not recognizing? And if I do need to change things, where should I start?
What you're asking for makes no sense - if these subDBs you want to create have no names, then how do you reference them?
depending on your node size, just using the duplicate-key support can probably handle what you need to do.
openldap-technical@openldap.org
-
Howard Chu -
ruben.soh＠rutgers.edu