1:mod:`btree` -- simple BTree database
2=====================================
3
4.. module:: btree
5   :synopsis: simple BTree database
6
7The ``btree`` module implements a simple key-value database using external
8storage (disk files, or in general case, a random-access `stream`). Keys are
9stored sorted in the database, and besides efficient retrieval by a key
10value, a database also supports efficient ordered range scans (retrieval
11of values with the keys in a given range). On the application interface
12side, BTree database work as close a possible to a way standard `dict`
13type works, one notable difference is that both keys and values must
14be `bytes` objects (so, if you want to store objects of other types, you
15need to serialize them to `bytes` first).
16
17The module is based on the well-known BerkelyDB library, version 1.xx.
18
19Example::
20
21    import btree
22
23    # First, we need to open a stream which holds a database
24    # This is usually a file, but can be in-memory database
25    # using io.BytesIO, a raw flash partition, etc.
26    # Oftentimes, you want to create a database file if it doesn't
27    # exist and open if it exists. Idiom below takes care of this.
28    # DO NOT open database with "a+b" access mode.
29    try:
30        f = open("mydb", "r+b")
31    except OSError:
32        f = open("mydb", "w+b")
33
34    # Now open a database itself
35    db = btree.open(f)
36
37    # The keys you add will be sorted internally in the database
38    db[b"3"] = b"three"
39    db[b"1"] = b"one"
40    db[b"2"] = b"two"
41
42    # Assume that any changes are cached in memory unless
43    # explicitly flushed (or database closed). Flush database
44    # at the end of each "transaction".
45    db.flush()
46
47    # Prints b'two'
48    print(db[b"2"])
49
50    # Iterate over sorted keys in the database, starting from b"2"
51    # until the end of the database, returning only values.
52    # Mind that arguments passed to values() method are *key* values.
53    # Prints:
54    #   b'two'
55    #   b'three'
56    for word in db.values(b"2"):
57        print(word)
58
59    del db[b"2"]
60
61    # No longer true, prints False
62    print(b"2" in db)
63
64    # Prints:
65    #  b"1"
66    #  b"3"
67    for key in db:
68        print(key)
69
70    db.close()
71
72    # Don't forget to close the underlying stream!
73    f.close()
74
75
76Functions
77---------
78
79.. function:: open(stream, *, flags=0, pagesize=0, cachesize=0, minkeypage=0)
80
81   Open a database from a random-access `stream` (like an open file). All
82   other parameters are optional and keyword-only, and allow to tweak advanced
83   parameters of the database operation (most users will not need them):
84
85   * *flags* - Currently unused.
86   * *pagesize* - Page size used for the nodes in BTree. Acceptable range
87     is 512-65536. If 0, a port-specific default will be used, optimized for
88     port's memory usage and/or performance.
89   * *cachesize* - Suggested memory cache size in bytes. For a
90     board with enough memory using larger values may improve performance.
91     Cache policy is as follows: entire cache is not allocated at once;
92     instead, accessing a new page in database will allocate a memory buffer
93     for it, until value specified by *cachesize* is reached. Then, these
94     buffers will be managed using LRU (least recently used) policy. More
95     buffers may still be allocated if needed (e.g., if a database contains
96     big keys and/or values). Allocated cache buffers aren't reclaimed.
97   * *minkeypage* - Minimum number of keys to store per page. Default value
98     of 0 equivalent to 2.
99
100   Returns a BTree object, which implements a dictionary protocol (set
101   of methods), and some additional methods described below.
102
103Methods
104-------
105
106.. method:: btree.close()
107
108   Close the database. It's mandatory to close the database at the end of
109   processing, as some unwritten data may be still in the cache. Note that
110   this does not close underlying stream with which the database was opened,
111   it should be closed separately (which is also mandatory to make sure that
112   data flushed from buffer to the underlying storage).
113
114.. method:: btree.flush()
115
116   Flush any data in cache to the underlying stream.
117
118.. method:: btree.__getitem__(key)
119            btree.get(key, default=None, /)
120            btree.__setitem__(key, val)
121            btree.__delitem__(key)
122            btree.__contains__(key)
123
124   Standard dictionary methods.
125
126.. method:: btree.__iter__()
127
128   A BTree object can be iterated over directly (similar to a dictionary)
129   to get access to all keys in order.
130
131.. method:: btree.keys([start_key, [end_key, [flags]]])
132            btree.values([start_key, [end_key, [flags]]])
133            btree.items([start_key, [end_key, [flags]]])
134
135   These methods are similar to standard dictionary methods, but also can
136   take optional parameters to iterate over a key sub-range, instead of
137   the entire database. Note that for all 3 methods, *start_key* and
138   *end_key* arguments represent key values. For example, `values()`
139   method will iterate over values corresponding to they key range
140   given. None values for *start_key* means "from the first key", no
141   *end_key* or its value of None means "until the end of database".
142   By default, range is inclusive of *start_key* and exclusive of
143   *end_key*, you can include *end_key* in iteration by passing *flags*
144   of `btree.INCL`. You can iterate in descending key direction
145   by passing *flags* of `btree.DESC`. The flags values can be ORed
146   together.
147
148Constants
149---------
150
151.. data:: INCL
152
153   A flag for `keys()`, `values()`, `items()` methods to specify that
154   scanning should be inclusive of the end key.
155
156.. data:: DESC
157
158   A flag for `keys()`, `values()`, `items()` methods to specify that
159   scanning should be in descending direction of keys.
160