Ask HN: BTree Alternative for Storing to Disk?
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. 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. Can you try to use a memory-mapped file, so the tree is always stored to disk, without a need of de/serialization? > Can you try to use a memory-mapped file Definitely do *not* use MMAP for this. 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. 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. The basic BTree structure isn't that complicated. Why not start with something simple?