-
Notifications
You must be signed in to change notification settings - Fork 2
Open
Description
We want the ability to delete records from the B+ tree. To do this, we will tombstone leaf nodes.
Because the B+ tree can store multiple values per key, we will delete by key/value pair. But crucially, we will match the values by offset only. This is pretty subtle so it should be documented carefully. That is, our function signature should look like:
func (t *BPTree) Delete(key []byte, valueOffset uint64) (bool, error) {The algorithm for deleting will be as follows:
- Find the first node matching
key. This is identical toFindtoday. - Call
.Next()for each matching key, update theleafPointerto have offset^uint64(0)(ie tombstone it). - Update
.Next()to skip tombstoned entries.
Metadata
Metadata
Assignees
Labels
No labels