Implement indices for Traces

The Spine trace implementation is a list of batches, each of which is a key-ordered collection of records. Different batch implementations make it differently easy to leap to the data for a key; the hash implementation lets you use hash values, the ord implementation lets you use binary search. In all cases, you need to independently look through each of the batches.

This design is handy if you would like to clone the list of batches and have an owned cursor through the collected batches.

At the same time, in many situations it is acceptable to borrow the trace reference, do a bounded amount of work, and then release the borrow. In these situations, we could implement and use a single index for each trace, with information for each key of the specific offsets it can be found (or not found) in each of the batches. This dramatically simplifies the cost of key lookups, reducing the amount of hashing and the random probing in memory for sparse updates. Ideally dense updates (many keys) would still result in an in-order traversal of memory, which might not be the case if we just use a HashMap as the index.

This is also where in the previous implementation of differential dataflow we slotted in a specialized index for small integer keys, based on vectors. This made each key lookup especially simple, and the index especially compact.

The issue does not name files, tests, or entry points. Start by locating the Spine trace and its hash and ord batch implementations, then compare them with the prior differential dataflow index design described here. Done means a trace-level index supports efficient key lookups while preserving an appropriate traversal strategy for dense updates.