During 2004-5, I designed and implemented a K-V object store on the top of BerkeleyDB. It served as the persistence layer for a number of applications my then

During 2004-5, I designed and implemented a K-V object store on the top of BerkeleyDB. It served as the persistence layer for a number of applications my then company developed for regulated industries. The approach was very similar. The current versions of objects were stored in a set of tables, while old versions were stored in separate tables. In order to reduce bloat, I employed a few fairly simple compression techniques. They were reasonably good. On desktop-class machines with a Pentium processor, 256 MB of RAM and spinning hard disks, searching a million objects completed in single digit seconds. Later, I added bit-mapped indices with dynamically self-adjusting bucket sizes that were determined based on locally-weighted densities along their respective dimensions. They reduced search time on a million objects to tens of milliseconds, with full history searched. The obvious downside was that there was no SQL for ad hoc queries! So, a command line shell was provided with Ruby as the language, talking to a C API behind the scenes. All in all, the system worked and scaled very well.