On Mon, 2004-04-19 at 07:04, D. Richard Hipp wrote: > Darren Duncan wrote: > > > > I think the simple answer is that SQLite uses a linked list which can't > > know where a page is until reading the next one, but other databases use > > something other than a linked list; they would trade a bit of complexity > > for speed. -- Darren Duncan > > > > The linked-list structure of overflow storage is part of the problem. > But the fact that SQLite uses synchronous I/O is also a factor. In > order to make BLOBs fast in SQLite, I would have to change to a different > indexing technique for overflow storage *and* come up with some kind > of cross-platform, asynchronous disk read mechanism.
D.R.Morrison (1968)'s PATRICIA would certainly be faster for indexing large objects. For those of you without google, PATRICIA is called "Crit-bit trees" by DJB, and "supports the following operations at high speed: * See whether a string x is in the tree. * Add x to the tree. * Remove x from the tree. * Find the lexicographically smallest string in the tree larger than x, if there is one. It essentially works by storing a compressed pointer to the first unequal bit in the key. This means comparisons aren't necessary to traverse the nodes (but they can be needed to add nodes!) http://cr.yp.to/critbit.html http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/ Asynchronous read isn't necessary, but vectored reads are. Consider readv() POSIX 1003.1-2001 -- in fact, you could probably make result-fields return a struct iovec * that would "point" to the value within the database. Finally, it may be worthwhile to finally allow some portions of the database to be stored outside the main file and only store indexes in the main file. This can give huge performance increases for large blobs and wouldn't (necessarily) require a file format change if older programs were prepared for the fact that they might not be able to do anything useful to the value returned :) --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]