3 ms·
Wow! Obvious in hindsight! Do any databases use this or similar tricks?
by willvarfar 5y ago
Wow! Obvious in hindsight!
Do any databases use this or similar tricks?
- bartlomieju 5y agoBuntDB [0] from @tidwall uses this package as a backing data structure. And BuntDB is in turn used by Tile38 [1] [0] https://github.com/tidwall/buntdb https://github.com/tidwall/buntdb [1] https://github.com/tidwall/tile38 https://github.com/tidwall/tile38
- jlokier 5y agoYes. Even better, a good database will avoid traversing the blocks and path, when the key is close enough to the previous lookup's hint, making all but the first lookup in a nearly-consecutive sequence take O(1) instead of O(log N) where N is the size of the tree, and runs of n nearly-consecutive operations take O(n + log N) instead of O(n log N).