how to form tree database structure using lmdb

Question

Here I'm trying to create graph database whose structure will look following. As I keep adding more nodes, I don't see the depth of the tree increasing. Can one suggest what I might be doing wrong here?

       A:1
     /    \
    B:2   C:3
  /          \
D:4          E:5

    >>> import lmdb
    >>> env = lmdb.open("treedb.lmdb")
    >>> txn = env.begin(write = True)
    >>> txn.stat()
    {'psize': 4096, 'depth': 0, 'branch_pages': 0, 'leaf_pages': 0, 'overflow_pages': 0, 'entries': 0}
    >>> txn.put('root'.encode('utf-8'),json.dumps({'A':1}).encode('utf-8'))
    True
    >>> txn.stat()
    {'psize': 4096, 'depth': 1, 'branch_pages': 0, 'leaf_pages': 1, 'overflow_pages': 0, 'entries': 1}
    
    >>> txn.put('A'.encode('utf-8'), json.dumps({'A':{'B':2}}).encode('utf-8'))
    True
    >>> txn.stat()
    {'psize': 4096, 'depth': 1, 'branch_pages': 0, 'leaf_pages': 1, 'overflow_pages': 0, 'entries': 2}
    >>>
    >>> txn.put('A'.encode('utf-8'), json.dumps({'A':{'C':3}}).encode('utf-8'))
    True
    >>>
    >>> txn.stat()
    {'psize': 4096, 'depth': 1, 'branch_pages': 0, 'leaf_pages': 1, 'overflow_pages': 0, 'entries': 3}
    >>>
    >>> txn.put('B'.encode('utf-8'), json.dumps({'B':{'D':4}}).encode('utf-8'))
    True
    >>> txn.put('C'.encode('utf-8'), json.dumps({'C':{'E':5}}).encode('utf-8'))
    >>> txn.stat()
{'psize': 4096, 'depth': 1, 'branch_pages': 0, 'leaf_pages': 1, 'overflow_pages': 0, 'entries': 5}

I keep adding more childs but still the tree remains flat. Almost it is just a key:value DB instead of graph. I must be missing something which I don't understand. — Dibyendu Dey, Aug 20 '21 at 01:56
Do you need traversal queries only? Or you need to also query by properties? — amirouche, Aug 20 '21 at 08:12

amirouche · Answer 1 · 2022-05-14T10:29:31.333

First it is unclear what you are trying to achieve with txn.stats.

Second, str.encode is the "poor man" packing function, you need lexicographic packing into bytes preserving natural type order (ref: python:fdb.tuples.pack)

If you want to go from a parent to children and back, given the following tree:

a
|_b
|_c
|_d
|_e
  |_f
  |_g
  |_h

Given the following notation key -> value, you can build the following okvs schema:

a -> properties
a.b -> properties
a.c -> properties
a.d -> properties
a.e -> properties
a.e.f -> properties
a.e.g -> properties
a.e.h -> properties

If say, you have the node a.e.g you can retrieve the parent by removing the last component to obtain a.e, then to query all children of a.e, you query the range of keys that have as prefix (startswith) a.e..

See https://stackoverflow.com/a/69317404/140837

Really the dot . as separator is a hack, look into python-lexode.

how to form tree database structure using lmdb

1 Answers1