Skip to content

Panic during delete #9

@Panky-codes

Description

@Panky-codes

Steps to reproduce the panic:

  • Set the degree to be two (b=2)
  • Add: a, b, c, d, e, f, g, h, j
  • Remove: j,i,h,g

I adapted the delete_works test case with the above scenario.

This results in the following panic:

running 1 test
test btree::tests::delete_works ... Keys [Key("f")] idx 1
thread 'btree::tests::delete_works' panicked at src/btree.rs:334:22:
removal index (is 1) should be < len (is 1)

This is how the tree looks after deleting j,i,h:

Node at offset: 122880
|->Keys: [Key("d")]
|->Children: [Offset(81920), Offset(126976)]
   |  Node at offset: 81920
   |  |->Keys: [Key("b")]
   |  |->Children: [Offset(24576), Offset(49152)]
   |     |  Node at offset: 24576
   |     |  |->Key value pairs: [KeyValuePair { key: "a", value: "a" }, KeyValuePair { key: "b", value: "b" }]
   |     |  Node at offset: 49152
   |     |  |->Key value pairs: [KeyValuePair { key: "c", value: "c" }, KeyValuePair { key: "d", value: "d" }]
   |  Node at offset: 126976
   |  |->Keys: [Key("f")]
   |  |->Children: [Offset(69632), Offset(131072)]
   |     |  Node at offset: 69632
   |     |  |->Key value pairs: [KeyValuePair { key: "e", value: "e" }, KeyValuePair { key: "f", value: "f" }]
   |     |  Node at offset: 131072
   |     |  |->Key value pairs: [KeyValuePair { key: "g", value: "g" }]

When we delete g, we do the following:

  • we merge the e, f node with the g node
  • delete parent node f which is resulting in panic at btree.rs:334

I think we need to add a condition which checks the length of the node for underflow, before removing the key at btree.rs:334. If it is an underflow, then maybe we need to move the node and its children up?

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions