from Hacker News

Ask HN: BTree Alternative for Storing to Disk?

by JoeOfTexas on 8/17/24, 6:45 AM with 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.

  • by hiAndrewQuinn on 8/17/24, 7:30 AM

    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.

  • by idiocrat on 8/17/24, 3:03 PM

    Can you try to use a memory-mapped file, so the tree is always stored to disk, without a need of de/serialization?

  • by adastra22 on 8/17/24, 7:02 AM

    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.