Ask HN: BTree Alternative for Storing to Disk?
7 points by JoeOfTexas 10 months ago | 6 commentsThe 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 agoI 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 agoCan 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.
- apavlo 10 months ago
- adastra22 10 months agoNo, 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 agoI 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 agoThe basic BTree structure isn't that complicated. Why not start with something simple?
- adastra22 10 months ago
- JoeOfTexas 10 months ago