MrCroxx / RunKV

[WIP] An experimental cloud-native distributed KV engine for OLTP workload.
MIT License
68 stars 7 forks source link

[RFC] feat: seek return Ordering for binary search #11

Closed MrCroxx closed 2 years ago

MrCroxx commented 2 years ago

Make seek return an Ordering for binary search on iterators. With it, we can use a binary_search_by(Future<Output=Ordering>) pattern for binary search seek.

Note: There is no built-in async binary search support. IMO, seek on Seek::Random is just I want to perform binary search seek, but the existing interfaces seems enough. Not sure if this is necessary.

    /// `seek` returns [`Ordering`] for binary search, which incidates the comparison between
    /// expection key and result key. Seeking for first or last postion always returns
    /// `Ordering::Equal` .
MrCroxx commented 2 years ago

Codecov Report

Merging #11 (85e0646) into main (560810a) will decrease coverage by 0.08%. The diff coverage is 95.00%.

Impacted file tree graph

@@            Coverage Diff             @@
##             main      #11      +/-   ##
==========================================
- Coverage   93.84%   93.76%   -0.09%     
==========================================
  Files          12       12              
  Lines         569      577       +8     
==========================================
+ Hits          534      541       +7     
- Misses         35       36       +1     
Impacted Files Coverage Δ
storage/src/iterator/block_iterator.rs 98.26% <88.88%> (-0.55%) :arrow_down:
storage/src/iterator/concat_iterator.rs 98.47% <100.00%> (+0.03%) :arrow_up:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 560810a...85e0646. Read the comment docs.

MrCroxx commented 2 years ago

Duplicated with #14 , close.