Re: [php] Mysql - Spaltenabfrage

[Kristian Köhntopp <kk_(at)_netuse.de>]

Alex Killing wrote:
> zum gesamten Durchsuchen einer Tabelle superschnell. Die Zugriffszeit
> ist durch log(n) begrenzt (Basis 2, n ist die Anzahl der Datensätze). 

Tatsächlich ist es in den meisten Datenbanken noch schneller. Wenn b die
Blockgröße der Datenbank ist (Oracle-Default: 2048 Byte) und l die mittlere
Länge einer Zeile in Deiner aktuellen Tabelle (z.B. 100), dann passen im 
Mittel b/l Datensätze in einen Block und Du bekommst einen Index mit der 
Zugriffszeit log(b/l, n) (also Basis b/l statt 2). Bei einer Tabellengröße 
von einer  Million Datensätzen sind dies also nicht 20 Zugriffe (Basis 2), 
sondern  bloß ln(1000000)/ln(20) = ca. 5 Zugriffe.

Keine Ahnung, wie MySQL das macht, aber möchte fast glauben, daß die auch
keine Binärbäume, sondern n-Bäume verwenden, weil die noch langsamer
in der Komplexität ansteigen.

Kristian

-- 
Kristian Köhntopp, NetUSE Kommunikationstechnologie GmbH
Siemenswall, D-24107 Kiel, Germany, +49 431 386 436 00
Using PHP3? See our web development library at
http://phplib.shonline.de/ (GPL)