seeing constant time inserts - that should be impossible, right?

Hi all,

My problem may not actually be a problem. I believe berkeley db je uses btrees for indexing. I am making MANY MANY inserts and no matter how big the index and database grow, my insert times are still constant. Theoretically, this is impossible due to the nature of btrees, right? Yet my experimental results show otherwise. Am I doing something wrong, or is Berkeley making use of the fact that my records are being inserted in the order that they ought to be sorted by key? In other words, every record's key value is greater than the key value of the previously inserted record.

I'm making millions of inserts into my database. I've enabled setSortedDuplicates(true) and I've checked the # of records on the database to make sure my rows have actually been inserted. I've either been doing all transactional inserts or all non-transactional inserts and using System.currentTimeMillis() as my key/index. I have traversed the database to make sure my records were actually being sorted by key and they were.

I've provided some code.

Please, any help would be greatly appreciated.

Thanks,
Julian

<code>

private void initDB(String[] args) {
/* Create a new, transactional database environment. */
boolean transaction = Boolean.valueOf(args[2]);
EnvironmentConfig envConfig = new EnvironmentConfig();
envConfig.setTransactional(transaction);
envConfig.setAllowCreate(true);
envConfig.setLocking(true);

try {
env = new Environment(new File(args[7]), envConfig);

EnvironmentMutableConfig envMutableConfig =
new EnvironmentMutableConfig();
envMutableConfig.setCacheSize(52428800); //in bytes

env.setMutableConfig(envMutableConfig);

/*
* Make a database within that environment. Because this will be used
* as a primary database, it must not allow duplicates. The primary key
* of a primary database must be unique.
*/
if (transaction) {
txn = env.beginTransaction(null, null);
}

DatabaseConfig dbConfig = new DatabaseConfig();
dbConfig.setTransactional(transaction);
dbConfig.setAllowCreate(true);
dbConfig.setSortedDuplicates(true);
dbConfig.setExclusiveCreate(false);
dbConfig.setDeferredWrite(!transaction); //not a typo, deferredWrite and transactional are mutually exclusive

if (transaction) {
canMessageDb = env.openDatabase(txn, "canMessageDb", dbConfig);
} else {
canMessageDb = env.openDatabase(null, "canMessageDb", dbConfig);
}

/*
* In our example, the database record is composed of an integer key
* and and instance of the MyData class as data.
*
* A class catalog database is needed for storing class descriptions
* for the serial binding used below. This avoids storing class
* descriptions redundantly in each record.
*/
DatabaseConfig catalogConfig = new DatabaseConfig();
catalogConfig.setTransactional(transaction);
catalogConfig.setAllowCreate(true);
catalogConfig.setExclusiveCreate(false);

if (transaction) {
catalogDb =
env.openDatabase(txn, "catalogDb", catalogConfig);
} else {
catalogDb =
env.openDatabase(null, "catalogDb", catalogConfig);
}

StoredClassCatalog catalog = new StoredClassCatalog(catalogDb);

/*
* Create a serial binding for MyData data objects. Serial
* bindings can be used to store any Serializable object.
*/
dataBinding = new SerialBinding(catalog, CanMessage.class);
keyBinding = TupleBinding.getPrimitiveBinding(Long.class);

if (transaction) {
txn.commit();
txn = null;
}
} catch (DatabaseException dbe) {
dbe.printStackTrace();
} catch (Exception ex) {
ex.printStackTrace();
}
}

public void storeCanMessage(String[] args) throws DatabaseException {
try {
int num_messages = Integer.valueOf(args[0]);
int commit_buffer_size = Integer.valueOf(args[1]);
System.err.println("NonTransactional writing " + num_messages + " records with a " + commit_buffer_size + " record commit buffer");

/* DatabaseEntry represents the key and data of each record. */
DatabaseEntry keyEntry = new DatabaseEntry();
DatabaseEntry dataEntry = new DatabaseEntry();

Long key;
byte[] temp = new byte[8];
for (int j = 0; j < 8; j++) {
temp[j] = (byte) (Math.random() * Byte.MAX_VALUE);
}

writeStart = System.currentTimeMillis();

for (int i = 0; i < num_messages; i = i + commit_buffer_size) {
for (int j = 0; j < commit_buffer_size; j++) {
CanMessage aCanMessage = new CanMessage((short) (Math.random() * 256), (int) (Math.random() * 65536), ((short) (Math.random() * 1)), temp);

key = System.currentTimeMillis();

keyBinding.objectToEntry(key, keyEntry);
dataBinding.objectToEntry(aCanMessage, dataEntry);

if (canMessageDb.put(null, keyEntry, dataEntry) != OperationStatus.SUCCESS) {
System.err.println("OMG");
}

}
}

writeEnd = System.currentTimeMillis();
System.err.println("Took " + (writeEnd - writeStart) + " ms, which comes to " + ((double) num_messages / (double) (writeEnd - writeStart)) + " writes/ms");
} catch (Exception ex) {
Logger.getLogger(BerkeleyDatabase.class.getName()).log(Level.SEVERE, null, ex);
}
}

public static void main(String[] args)
{
...
myDb.storeCanMessage(args);
}
</code>