Wo binäre Suche schneller, mit Array oder StringList?

[Namenloser]

Zitat von Dejan Vu:

Zitat von Namenloser:

Der normale Standard-Index ist bei gängigen Datenbanken immer ein balancierter Baum, wenn man nichts anderes spezifiziert.

Ein B-Baum ist aber kein 'balancierter Baum' (na ja, irgendwie schon).

Natürlich ist der balanciert? Erfüllt genau die Definition von Wikipedia: „Ein balancierter Baum (englisch oft self-balancing tree) ist in der Informatik ein Spezialfall der Datenstruktur Baum, der eine maximale Höhe von c⋅log(n) garantiert, wobei n die Anzahl der Elemente im Baum angibt und c eine von n unabhängige Konstante ist.“
Außerdem muss es ja nicht zwangsläufig ein B-Baum sein. Ich weiß nicht, was da in der Praxis zum Einsatz kommt. Auch wenn es gut sein kann, dass es tatsächlich ein B-Baum ist. Auf jeden Fall ist es aber ein balancierter Baum.

Zitat von Dejan Vu:

Geht das mit SQLite? Ich würde zeit BETWEEN t1 and t2 nehmen.

Keine Ahnung, ich mach nur alle paar Jahre mal was mit SQL.

Zitat von Dejan Vu:

Zitat von Namenloser:

...fast gleich schnell (O(log n))

Die Basis des Logarithmus ist aber sehr groß: PageSize div SizeOf(Key). Das geht gegen O(1).

Ja, „fast gleich schnell“ in der Praxis.

[BUG]

Zitat von Namenloser:

Außerdem muss es ja nicht zwangsläufig ein B-Baum sein. Ich weiß nicht, was da in der Praxis zum Einsatz kommt.

Ich würde wetten das es eine Variante des B+ Baums ist ... Datenbankers Liebling

...

Ich hab nachgeschaut: B+ Tree für Daten und B Trees für Indices.

[Dejan Vu]

@Namenloser: Ich schrieb ja, das ein Bayer-Baum auch balanciert ist, nur ist ein 'B'-Baum kein b-alancierter Baum sondern ein B-ayer-Baum und 'fast gleich schnell' wird bei einigen RDBMS zum 'gleich schnell', wegen der Implementierung des Indexes als B+-Baum. Ich habe ja keine Aussage von Dir negiert sondern nur präzisiert.