countedBTree deleteID erroneous behavior
shichuzhu opened this issue · 0 comments
shichuzhu commented
A new bug is found in the Btree---the delete operation does not work when the number of elements exceeds the block size.
We have set the block size to 10. We first insert 30 items to the CountedBTree and the delete items 10 to 19. But if we call getIDs() after deletion. only item 10 and 15 is shown to be deleted., the rest are not deleted. Now, if we reinsert the "supposedly" deleted elements in the tree. we now have redundant entries---items 11 to 19 appear twice.
This use case appears when we want to delete a range of elements in the tree, sort them by a different order and reinsert them at their original position. The result of the running test:
Get whole list of 30 elements:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
after deletion from 10 with count of 10
deleted counts: 10
deleted entries: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
whole count of list after deletion: 28
whole list after deletion: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
After insert again reversed deleted entries:
whole counts: 38
whole list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
The test code can be found here