-
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 toFind
today. - Call
.Next()
for each matching key, update theleafPointer
to have offset^uint64(0)
(ie tombstone it). - Update
.Next()
to skip tombstoned entries.
Metadata
Metadata
Assignees
Labels
No labels