[erlang-questions] B-trees

Richard A. O'Keefe <>
Thu Dec 8 08:47:29 CET 2016



On 8/12/16 7:36 PM, Walter Weinmann wrote:

Every time I've tried to use B-trees, I've run SPLAT!
into a wall:
  - the B-tree data structure wants to read and write single
    pages
  - and wants to store a fairly large minimum number of
    keys on a page
  - disc pages aren't *that* big
  - my keys would usually be small but *might* be large
    (well, kilobytes rather than megabytes, but that's enough
    to mess up B-trees)
  - dealing with this meant storing hash(Key) -> {Key,Value}
    instead, which meant
    * having to handle duplicates that aren't real duplicates
      (again rare, but since it *could* happen...)
    * losing the ordering properties of the B-tree.

How do you handle the keys-might-be-large problem?

For what it's worth, LMDB does traversal; if emdb doesn't, so much
the worse for emdb.  LMDB has some very nice reliability properties.



More information about the erlang-questions mailing list