Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Concurrency issues are a challenge, but a bigger problem is when designing a copy-on-write B-Tree, which is what I did. With such a design, any change to a node causes a replacement to be allocated, and then the pointer into it must be changed too. This means that the referencing node must be copied, and so on.

If only the parent pointer needs to be changed (and up to the root), this isn't a big deal considering that B-Trees aren't very deep, and a good implementation will cache modifications anyhow.

When sibling pointers are introduced, a copy-on-write B-Tree will on average need to read and rewrite half of the B-Tree on every modification. For this reason, I don't use sibling pointers.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: