WIP safe and sane B-Tree rewrite

Total minimal rewrite of BTree to not use copy/clone at all, and to generally avoid unnecessary mutations. I have not yet implemented the "miscellaneous" collection things like iterators, Ord, Eq, Hash, etc as I want to nail the core stuff down first. 

There is one substantial drawback to my implementation: it doesn't allow configuration of `B`. The benefit of this is that the nodes are made of `[T,..n]`'s instead of Vecs, putting more data contiguously and reducing the amount of indirection. I have done this under @aturon's recommendation that it would be better to write a BTree implementation that would benefit from the future possibility of generic integer arguments being available (I am not saying they will be added).

One consequence of this is that I currently store the Keys/Values in Options, because it's not clear to me if there's a safe way to work with partially intialized arrays, or to tell Rust to "forget" some or all of the array and not try to run destructors on the elements. I would *love* if someone could show me how to do that.

In addition, right now I do a *lot* of indexing which could probably be replaced with iterators to avoid bounds checks. I'm also not leveraging `copy` instrinsics to bulk shift the elements around. This first draft is emphasizing correctness and safety over performance, but in a way that's easily upgradable. I hope to have the time to start tuning the implementation in the coming days,

The actual code is literally 25% just comments describing the fairly complex logic of a BTree. I've tried to chunk things out into "grokable" functions where possible so that everyone understands what's going on. 

Finally, as a quick sanity check, I ran treemap's bench suite on btree (`make check-collections -j8 PLEASE_BENCH=1`):
```
test treemap::bench::find_rand_100                         ... bench:        74 ns/iter (+/- 5)
test treemap::bench::find_rand_10_000                      ... bench:       164 ns/iter (+/- 3)
test treemap::bench::find_seq_100                          ... bench:        76 ns/iter (+/- 2)
test treemap::bench::find_seq_10_000                       ... bench:       115 ns/iter (+/- 2)
test treemap::bench::insert_rand_100                       ... bench:       126 ns/iter (+/- 2)
test treemap::bench::insert_rand_10_000                    ... bench:      1025 ns/iter (+/- 16)
test treemap::bench::insert_seq_100                        ... bench:       507 ns/iter (+/- 19)
test treemap::bench::insert_seq_10_000                     ... bench:       834 ns/iter (+/- 15)

test btree::bench::find_rand_100                           ... bench:        86 ns/iter (+/- 4)
test btree::bench::find_rand_10_000                        ... bench:       165 ns/iter (+/- 2)
test btree::bench::find_seq_100                            ... bench:        86 ns/iter (+/- 2)
test btree::bench::find_seq_10_000                         ... bench:       117 ns/iter (+/- 1)
test btree::bench::insert_rand_100                         ... bench:       270 ns/iter (+/- 10)
test btree::bench::insert_rand_10_000                      ... bench:       598 ns/iter (+/- 18)
test btree::bench::insert_seq_100                          ... bench:       386 ns/iter (+/- 8)
test btree::bench::insert_seq_10_000                       ... bench:       459 ns/iter (+/- 4)
```

As you can see, my implementation is generally competitive with treemap, and is substantially faster during large insertion workloads. And as discussed above, I haven't even begun to tune it; my choice of B is largely arbitrary!

If anyone is a low-level optimizing expert, or just knows good BTree design/tuning, I'd love to get any feedback on this work. If anyone has any other ideas or questions, I'm more than happy to discuss this with you!

Spaces