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]

Reply via email to