-
Notifications
You must be signed in to change notification settings - Fork 14
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Bulk remove items from TreeIndex: remove_range
#120
Comments
Yes, that kind of API would be helpful, however, I wouldn't expect a huge performance gain, since there can always be other threads inserting values in that range, and thus disallowing me to implement something similar to I'll implement something next week. |
For my use case at least the key is always atomically incrementing, I keep an Thank you again for your continued development and upkeep of |
In my opinion, implementing a new data structure for the purpose is optimal since the ever-increasing key assumption will enable a lot of optimization; I think, a ring-buffer-like data structure will be better than a tree (didn't think about it seriously yet). On the other hand, implementing Anyway, I'll firstly focus on optimizing the |
|
OK, I tried to implement On the other hand, O(1) bulk removal seems to be quite doable in a couple of weeks. So, in this issue, as originally suggested, I'll directly implement |
remove_range
O(1) bulk removal would be more than optimal. Also absolutely no rush on this, and thank you again! |
You're welcome! Just note that, O(1) will be a best-case scenario, and most of the time, removing entries close to start and end bounds will require tree traversal. |
FYI: uploaded SCC 2.0.9 which contains an unoptimized version of |
Still, several issues with remove_range.
Sub-trees are directly removed if they are definitely contained in the specified range.
FYI: uploaded 2.0.14 that contains the proposed optimized version of |
Would it be possible to add an efficient
remove_range
ordrain
-like API onTreeIndex
?I'd like to use a
TreeIndex<u64, Arc<[u8]>>
as a queue where many readers keep a pointer into it by index, so they can keep up at their own pace, and periodically clear old entries like.remove_range(..least_recent_index)
. The alternative would be just repeated calls to.remove
with a decrementing counter until it returns false.The text was updated successfully, but these errors were encountered: