Paul Nash wrote:

Regard the insertion efficiency. I know nothing about SQLite internals and litle about B-trees which I understand SQLite uses, but a look at Knuth provides some tweaks to the B-tree algorithms which improve performance. Mrs.Brisby suspects MySQL is packing indexes and this is the first of the refinements that Knuth mentions (AOCP Vol 2 pg 476).


See the header comment on


http://www.sqlite.org/cvstrac/getfile/sqlite/src/btree.c

The B-tree algorithm in SQLite is based on Knuth.  Specifically,
it uses the unpublished variable-length key algorithm attributed
to T. H. Martin on page 477 near the bottom and the "overflow"
algorithm of Bayer and McCreight described in the following
paragraphs.

See also section 3.0 of the file format description at

http://www.sqlite.org/fileformat.html

I'm not sure what you or Mrs.Brisby mean by "packing".

--
D. Richard Hipp -- [EMAIL PROTECTED] -- 704.948.4565


--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]



Reply via email to