record size quantization changes record sizes for v0 indexes

• v0 indexes are the first index version that mongo provided
• v1 indexes are a different index format introduced with version 2.0. 2.0+ versions continue to support v0 indexes, but new and rebuilt indexes in these versions use the v1 format by default

v1 indexes are allocated as a an 8176 byte bucket with a 16 byte header combining to form a record of size 8192 bytes.

v0 indexes are allocated as an 8192 byte bucket with a 16 byte header combining to form a record of size 8202 bytes in versions 2.2 and earlier. The record quantization behavior in the current master increases the record size to 9216 bytes. This means that new v0 index records will be 12% larger than older v0 index records, with the extra space being unused.

Furthermore: When updating a btree, index records representing buckets within the btree may be allocated and deallocated. Because the new record size is larger than the old record size, old deleted records will not be reused. This could lead to fragmentation of the index collection.

Here is a test printing sizes for various indexes (the record headers are excluded from the reported sizes):

c = db.c;

function printIndexSize( nKeys, indexOptions ) {

    c.drop();

    c.ensureIndex( { a:1 }, indexOptions );

    for( i = 0; i < nKeys; ++i ) {

        c.save( { a:i } );

    }

    print( 'version: ' + indexOptions.v + ' nKeys: ' + nKeys + ' size: ' + c.stats().indexSizes.a_1 );

}

printIndexSize( 1e0, { v:0 } );

printIndexSize( 1e2, { v:0 } );

printIndexSize( 1e4, { v:0 } );

printIndexSize( 1e5, { v:0 } );

printIndexSize( 1e0, { v:1 } );

printIndexSize( 1e2, { v:1 } );

printIndexSize( 1e4, { v:1 } );

printIndexSize( 1e5, { v:1 } );

Results for 2.2

version: 0 nKeys: 1 size: 8192

version: 0 nKeys: 100 size: 8192

version: 0 nKeys: 10000 size: 376832

version: 0 nKeys: 100000 size: 3702784

version: 1 nKeys: 1 size: 8176

version: 1 nKeys: 100 size: 8176

version: 1 nKeys: 10000 size: 286160

version: 1 nKeys: 100000 size: 2812544

Results for master

version: 0 nKeys: 1 size: 9200

version: 0 nKeys: 100 size: 9200

version: 0 nKeys: 10000 size: 423200

version: 0 nKeys: 100000 size: 4158400

version: 1 nKeys: 1 size: 8176

version: 1 nKeys: 100 size: 8176

version: 1 nKeys: 10000 size: 286160

version: 1 nKeys: 100000 size: 2812544