search

dataspread / dataspread-web

http://dataspread.github.io
135 stars 31 forks source link

countedBTree deleteID erroneous behavior #208

Closed shichuzhu closed 6 years ago

shichuzhu commented 6 years ago

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