perf: Optimize BTree search using binary search

ie-Yoshisaur commented 4 months ago

Description

This pull request optimizes the search function in the BTree implementation by replacing the linear search with a binary search algorithm. This change significantly improves the search performance, especially for large trees, without altering the existing functionality.

The optimization is achieved by modifying the search method in the BTree struct to use the binary_search method on the keys vector instead of a while loop. This change reduces the time complexity of searching within a node from O(n) to O(log n), where n is the number of keys in the node.

Type of change

[x] New feature (non-breaking change which adds functionality)

Implementation Details

The main changes are in the search method of the BTree struct:

Replaced the while loop with binary_search method on the keys vector.

Benchmark Results

Environment: MacOS 14.5, Apple M1 Pro, 32 GB RAM Dataset: 1,000,000 random integers for insertion, 1,000,000 searches for the key 500,000

Before optimization:

Insertion: 3.002587333s
Search: 2.334683584s

After optimization:

Insertion: 2.998482583s
Search: 288.659458ms

Note: Insertion time remains largely unchanged, as expected.

Checklist:

[x] I ran the following commands using the latest version of rust nightly.
[x] I ran cargo clippy --all -- -D warnings just before my last commit and fixed any issue that was found.
[x] I ran cargo fmt just before my last commit.
[x] I ran cargo test just before my last commit and all tests passed.
[x] I checked CONTRIBUTING.md and my code follows its guidelines.

All existing tests pass with the new implementation. No new tests were added as the existing ones adequately cover the modified functionality.

codecov-commenter commented 4 months ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 95.08%. Comparing base (65ca19d) to head (b772765).

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #767 +/- ## ======================================= Coverage 95.07% 95.08% ======================================= Files 309 309 Lines 22781 22788 +7 ======================================= + Hits 21660 21667 +7 Misses 1121 1121 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

ie-Yoshisaur commented 3 months ago

By the way: would you like to spend some more time with this class?

Of course! I’ll work on fixing that issue and submit a PR soon.

TheAlgorithms / Rust