undefined | Better HN

0 pointsCapricorn24811y ago0 comments

> will be updated into into a single-file b-tree structure

I'm not knowledgeable on this, but my understanding was a b-tree is a way of sorting values that could be ordered in a certain way. Like this would be a b-tree of IDs

```

            [8]

           /   \

      [3, 5]   [10, 12]

     / | \     / | \  

  [1] [4] [6,7] [9] [11, 13]

```

You traverse by comparing your needle to the root node and going left or right depending on the results.

How is that done with configuration options? That seems like it would just be a regular hashmap which is already efficient to read. What would a b-tree of key/values even look like that wouldn't be less efficient than a hashmap?

0 comments

remram1y ago

Each number in your btree would actually be a key-value pair. So you can find the key fast, and then you have the value.

Databases including SQLite usually use b+tree for tables (a variant where only the leaves have data, the interior nodes only have keys) and regular btrees for indexes.

lucianbr1y ago

A hash table makes sense in memory. If it's loaded just right for fast access, it has holes - empty entries. That makes little sense if you are building a file that will be transferred to many places over the internet. Bandwith waste would be significant.

So it might seem that simply enumerating the data (sorted or not) would be a better option for a file. (After all, the receiver will read everything anyway.) I guess frequent updates make this inefficient, so a tree helps.

j / k navigate · click thread line to collapse