Assume I have 930 milliom records.

Doing a binary search takes 30 disk-reads, which I think, are too slow.

1. Is MySQL index a B-tree ?

2. Can I create an auxilliary index table (ie index of index) to speed up
the search ?

Thanks for advice.

Op 13-3-2010 9:48, sl@my-rialto schreef:
i presume you do mean 930 million ?

than you should buy a quicker disk...

read the docs...

this question i would like to leave to the experts.. ;-)


--
Luuk

Luuk:

Oh, c'mon Luuk! :-)

With these numbers, even if the records are only half a kilobyte, it's
going to be a 1TB-disk to store the data. Do you know extremely fast
disks of this size, that really would make a difference in this case?


MySQL offers the BTREE index option, yes. I believe the InnoDB engine
uses them by default.
Here's a document for starters
http://www.informit.com/articles/article.aspx?p=377652


Here's a paper on that:
http://www.stanford.edu/class/cs276a...ant-ravela.pdf



--
Erick

Erick T. Barkhuis wrote:
I can't think that anyone else than home users would use just one hard disk,
the database servers I have seen all uses some kind of raided system, and you
can with the right raid get a multiple smaller hard drives to be far faster
than just one big one.



--

//Aho

J.O. Aho wrote:
Yes. the bottleneck in disks is generally seek time.

So smaller disks work better.

The other thing that dramatically speeds up disk is massive amounts of
RAM to cache it all in.

Op 13-3-2010 10:10, Erick T. Barkhuis schreef:
the complete record does not have to be read with MyISAM, because
indexes are stored in a separate file (see below)

and a 'quicker disk' can also mean that you have to do some optimization
on OS-level, like pagesize/blocksize, cache, etc.
(or RAID, as J.O.Aho suggested)

<quote>
The particular details of index implementations vary for different MySQL
storage engines. For example, for a MyISAM table, the table's data rows
are kept in a data file, and index values are kept in an index file. You
can have more than one index on a table, but they're all stored in the
same index file. Each index in the index file consists of a sorted array
of key records that are used for fast access into the data file.</quote>


Because the index is in a separate file, this would be better way to
search the index, compared to InnoDB which combines data and indexes in
one physical file according to the same document.


--
Luuk

In article <hnfjgq$e3a$1 (AT) news (DOT) albasani.net>, "sl@my-rialto" <ecp_gen (AT) my-rialto (DOT) com> wrote:
And you think there might be some method that would use less than 30 reads for
a table with 930M rows?
What would be the point? Binary search is already about as fast as things are
going to get. If the index search is taking too long, then get a faster disk.

sl@my-rialto wrote:
30 disk reads for 930 million rows seems to be pretty good to me. If
it's too slow for you, you need to optimize your disk hardware.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex (AT) attglobal (DOT) net
==================

On Sat, 13 Mar 2010 09:55:15 +0000, The Natural Philosopher wrote:
This depends on load. I don't think MySQL is going to dispatch more than
one thread to read from multiple mechanisms at the same time during an
index search. Where RAIDs frequently gain speed is allowing multiple
processes to access different data without being blocked by unrelated
processes. (Well, yes, giant reads that span mulitple mechanism also can
benefit from parallelling, but really, most things never ever take
advantage of that because they're NOT after a 2 GB file as a whole,
they're after a particular part in that file, and already have a good
idea where that part is.)

Presumingly meaning "more disk arms (and thus probably more drives) are
better" rather than "less capacity is better".

That's gonna be a LOT of RAM... (Though prefetching a cache can be a
way to get that huge parallel read we talked about speeding things up
into useful memory, that's also some levels of tuning that may be better
to have handled someplace below the application layer that MySQL runs
in, or at least in deep cooperation with the lower levels. MOST of the
discussion about prefetch and MySQL is talking about how disappointing
the results are without also tuning the OS/filesystem to match, which is
often *not* a good idea on a host that runs other things as well.)

--
54. I will not strike a bargain with a demonic being then attempt to
double-cross it simply because I feel like being contrary.
--Peter Anspach's list of things to do as an Evil Overlord

On Sat, 13 Mar 2010 11:00:21 +0100, Luuk wrote:
.... and (apropos of other part of the thread) why InnoDB tends to gain a
bit on prefetching into a cache and MyISAM often doesn't or does so
little that it's not worth dedicating the memory to it.

--
40. I will be neither chivalrous nor sporting. If I have an unstoppable
superweapon, I will use it as early and as often as possible instead
of keeping it in reserve.
--Peter Anspach's list of things to do as an Evil Overlord