Re: [RFC] Use a 16-tree instead of a 256-tree for storing notes

On Wed, Aug 26, 2009 at 12:31, Johan Herland[off-list ref] wrote:

The 256-tree structure is considerably faster than storing all entries in a

This part is confusing. Was 256-tree better (as in "faster") then?

hash_map. Also, the memory consumption of the 256-tree structure is lower
than the hash_map, provided that you're only loading a few notes from a
"properly fanned-out" notes tree (i.e. 100000 notes in a 2/2/36 structure).
However, in the worst case (loading all 100000 notes), the memory usage of
the 256-tree structure (62.64 MB) is significantly worse than the hash_map
approach (10.25 MB).

This patch modifies the 256-tree structure into a 16-tree structure. This
significantly improves the memory situation. The result uses less memory
than both the 256-tree structure, and the hash_map approach, with a worst
case usage of 8.54 MB. Additionally, it seems to slightly improve the
runtime performance as well (probably because of the improved memory usage).