Ask HN: BTree Alternative for Storing to Disk?

7 points by JoeOfTexas 10 months ago | 6 comments
I am learning how to write a database for fun.

The issue with storing BTree to disk are the many operations for balancing on insert and deletion. I want a structure that is very simple to write to disk that doesn't require "balancing".

I tried making a HashTree for unique indexing which basically creates a new hashmap on each collisions, which would simplify appending the new hashmap into a file on disk. The issue was the hash function was difficult to craft that avoided going too far in depth through consecutive collisions.

I'm thinking there must be an alternative structure, but my limited understanding and research has yet to reveal anything better than BTree, LSM tree or Skiplists.

  • hiAndrewQuinn 10 months ago
    I don't think there is, but I'm glad to see you're interested in digging deep into the fundamentals. World's a better place with folk like you running around. :)

    My prior is that SQLite is based off of B-trees, fundamentally, and if anyone's going to know everything there is to know about efficiently and robustly reading and writing to a single local disk, it's probably going to be Dr. Richard Hipp.

    • idiocrat 10 months ago
      Can you try to use a memory-mapped file, so the tree is always stored to disk, without a need of de/serialization?
      • apavlo 10 months ago
        > Can you try to use a memory-mapped file

        Definitely do *not* use MMAP for this.

      • adastra22 10 months ago
        No, a BTree is the right tool for the job. How are you going to iterate keys in order in an index without sorted structure? And the BTtee is the purpose-designed structure for the job.
        • JoeOfTexas 10 months ago
          I was not thinking about ordering, that is an important point. I focused mainly on finding the "row" belonging to a unique key.

          Maintaining/designing the btree for innodb or postgres must be a nightmare with multithreading and the plethora of other features. I didn't want to dive into that rabbit hole.

          • adastra22 10 months ago
            The basic BTree structure isn't that complicated. Why not start with something simple?