[BUG] Fix bug with blockfile split

[sanketkedia]

Description of changes

Summarize the changes made by this PR.

• Improvements & Bug fixes

Consider the following scenario -

1. Block has keys {4, 5, 6, 7}
2. We want to insert key 2
3. Block is full so it needs to split
4. Split in the middle => block1: {4, 5}, block2: {6, 7}
5. [BUG] We insert the new key (i.e. 2) into the new block ALWAYS (i.e. here block2)
6. After insertion blocks are: block1: {4, 5}, block2: {2, 6, 7}
7. All the keys in Block1 are no longer < Keys in Block2 and we have an invariance violation thus a correctness issue!

Fix is to NOT ALWAYS insert the key into the new block but rather insert it into the block which fits in the range i.e. here in Block1.

Test plan

Added a unit test

• [x] Tests pass locally with pytest for python, yarn test for js, cargo test for rust

Documentation Changes

None

[vercel[bot]]

The latest updates on your projects. Learn more about Vercel for Git ↗︎

Name	Status	Preview	Comments	Updated (UTC)
chroma	✅ Ready (Inspect)	Visit Preview	💬 Add feedback	May 17, 2024 9:14pm

[github-actions[bot]]

Reviewer Checklist

Please leverage this checklist to ensure your code review is thorough before approving

Testing, Bugs, Errors, Logs, Documentation

• [ ] Can you think of any use case in which the code does not behave as intended? Have they been tested?
• [ ] Can you think of any inputs or external events that could break the code? Is user input validated and safe? Have they been tested?
• [ ] If appropriate, are there adequate property based tests?
• [ ] If appropriate, are there adequate unit tests?
• [ ] Should any logging, debugging, tracing information be added or removed?
• [ ] Are error messages user-friendly?
• [ ] Have all documentation changes needed been made?
• [ ] Have all non-obvious changes been commented?

System Compatibility

• [ ] Are there any potential impacts on other parts of the system or backward compatibility?
• [ ] Does this change intersect with any items on our roadmap, and if so, is there a plan for fitting them together?

Quality

• [ ] Is this code of a unexpectedly high quality (Readability, Modularity, Intuitiveness)