Support counted b-trees about tupl HOT 3 CLOSED

1. Add config option enabling counts for indexes, and at which level. Only level 1 support initially.
2. Add metadata describing that index supports counts.
3. Add logic to encode counts in the cursor implementation.
4. Update cursor skip method to utilize counts.

from tupl.

This is an optimization only for the cursor skip operation, and so an implementation is possible without incurring any overhead to anything else. Lazily update the counts, only in the bottom internal nodes. When a leaf node is dirtied, the count field is reset to zero, indicating "unknown". This happens already because the pointers are assumed to be 8 bytes.

The skip operation updates the counts if they are unknown, but it doesn't update the count if the leaf node is dirty. This avoids storing a count which might soon become incorrect. A "known" count is always stored with an offset of 1, allowing for the possibility of empty leaf nodes.

With this design, the skip code is not purely read-only, and optimizations are effective only when skip is run again over the same records. A configuration option can be added to disable skip-updated counting.

from tupl.

Change b561cfc

from tupl.