google / btree

BTree provides a simple, ordered, in-memory data structure for Go programs.
Apache License 2.0
3.9k stars 414 forks source link

Improve the iterate seek to O(logN) #25

Closed nolouch closed 6 years ago

nolouch commented 6 years ago

Hi, In our scenario, we frequently use the iterate, and the Less compare is expenses when key is large. This PR mainly improve the iterate location. uses binary search to quickly locates the start item. before:

BenchmarkSeek-4          3000000               452 ns/op
BenchmarkSeek-4          3000000               513 ns/op
BenchmarkSeek-4          3000000               454 ns/op
BenchmarkSeek-4          3000000               450 ns/op

after:

BenchmarkSeek-4         10000000               225 ns/op
BenchmarkSeek-4         10000000               222 ns/op
BenchmarkSeek-4         10000000               223 ns/op
BenchmarkSeek-4         10000000               224 ns/op
googlebot commented 6 years ago

Thanks for your pull request. It looks like this may be your first contribution to a Google open source project (if not, look below for help). Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

:memo: Please visit https://cla.developers.google.com/ to sign.

Once you've signed (or fixed any issues), please reply here (e.g. I signed it!) and we'll verify it.


What to do if you already signed the CLA

Individual signers
Corporate signers
googlebot commented 6 years ago

CLAs look good, thanks!

nolouch commented 6 years ago

PTAL @gconnell

gconnell commented 6 years ago

Thanks!