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]
