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

should call Less() fewer times when iterating #42

Open caterchong opened 2 years ago

caterchong commented 2 years ago

when calling DescendRange methods, an iteration is performed.

All items between [lessOrEqual, greaterThan ) are iterated.

Suppose there're n items in the range, I though Less function is called log(n) times.

However, Less is called more than n times as a matter of

if stop != nil && !n.items[i].Less(stop) {
                return hit, false
            }

Why make comparisons this way? I though if parent node can decide all its children are in the range, most Less(stop) call can be optimized out.

Are there anything wrong with this idea?

a180285 commented 1 year ago

@caterchong I have submitted a PR base on your idea.