Hi! On Oct 23, Phil Bitis wrote: > Hello, > > We want to be able to insert records into a table containing a billion > records in a timely fashion. > The table has one primary key, which I understand is implemented using > B-trees, causing insertion to slow by log N.
Corect. But for auto_increment field (on BIGINT, I believe ?), you'll have hundreds of keys on one key page, so logarithm base will be few hundreds, and log N should be just 3-5. That is, it should be only ~3-5 times slower as compared to the table with one hundred rows. > The key field is an auto_increment field. > The table is never joined to other tables. > Is there any way we could implement the index ourselves, by modifying > the MyISAM table handler perhaps? Or writing our own? Hmm, MyISAM can only do B-tree indexes. It won't be easy to add a completely different index algorithm to it. Writing your own table handler could be easier. > In our setup record n is always the nth record that was inserted in > the table, it would be nice to just skip n * recordsize to get to the > record. Right, assuming all records have the same length, you can just write nth record at the offest n * recordsize on inserts, and use the value of n as a key on reads. Of course, it's a very specialized storage engine, not that much of general use - but it's very specialized to handle your case, so it can be the fastest solution. > Also, could someone shed some light on how B-tree indexes work. Do > they behave well when values passed in are sequential (1, 2, 3, ...) > rather than random values? Yes. B-tree is always balanced: http://www.nist.gov/dads/HTML/btree.html Regards, Sergei -- __ ___ ___ ____ __ / |/ /_ __/ __/ __ \/ / Sergei Golubchik <[EMAIL PROTECTED]> / /|_/ / // /\ \/ /_/ / /__ MySQL AB, Senior Software Developer /_/ /_/\_, /___/\___\_\___/ Osnabrueck, Germany <___/ www.mysql.com -- MySQL General Mailing List For list archives: http://lists.mysql.com/mysql To unsubscribe: http://lists.mysql.com/[EMAIL PROTECTED]