[Feature] Add a BTree implementation

[TzviPM]

Would a btree implementation be good to include in this package? If so, I’d be happy to write one and some benchmarks for it. The only implementation I see so far on pub is https://pub.dev/packages/btree that's quite old and has outdated dart support.

[lrhn]

A proper self-balancing ordered data structure is something this package is missing.
I've considered (and at least partially written) AVL trees a few times, but never gotten around to adding it.

A good BTree implementation would work too. I'm actually not that familiar with BTrees, so let me check that I've understood it correctly: It's an n-ary tree structure where each node contains between n/2 and n entries, in sorted order, which count as separators for the child-nodes. You search by doing binary search on the node-embedded entries first, and if you don't find what you're looking for directly, you know between which two entries it must be, and recursively search the child node between them.
Then it's self-balancing in some way, probably a generalization of red/black trees, to ensure that all leaves are at the same level, which ensure some sort of "balance" (if each node has between n/2 and n separator entries, that's at most one extra step of binary search, which makes the total comparisons needed to find two leaf nodes at the same height by at most the height of the tree (which is O(log_n(N))).

Sounds reasonable.

It also sounds like a data structure that can be used as both the basis of a Set and a Map, since it's lookup based.
Just like we have SplayTreeMap and SplayTreeSet, we could have BTreeSet and BTreeMap.

[TzviPM]

Amazing; I'll start working on a PR