Wie werden B-Baum-Invarianten beibehalten, wenn Elemente in der Größe variieren?

Question

Für einen B-Baum der Ordnung m muss jeder Knoten außer der Wurzel m-1 bis 2m-1 Elemente enthalten, wobei jedes Element mindestens ein Schlüssel und möglicherweise auch einige zusätzliche Daten (z. B. ein Wert) ist. Dennoch muss jeder Knoten eine konstante Gesamtgröße aufweisen, die ausgewählt wird, um eine gute Leistung auf dem zugrunde liegenden Blockgerät bereitzustellen. Was passiert also, wenn Ihre Elemente variable Größe haben?

SQLite3 scheint für Anheften zusätzlichen Block große Stücke auf seinen Knoten über ein System zu haben, und MySQL können Sie die Größe Ihrer Datensätze deklarieren (zB können Sie Ihre Felder eingeben nicht nur Zeichenfolgen sein, aber Strings unter gewissen Größe) . Welche anderen Lösungen gibt es? Und was denken die Leute darüber, wenn sie sich gegenseitig auswählen?

bearbeiten: Und durch den vorhergehenden Satz, ich meine, was Datenbank-Entwickler darüber nachdenken, wenn entscheiden, ihre B-Bäume einen Weg, über den anderen zu implementieren?

(I in einem Datenbanken Natürlich bin gerade jetzt, also ist ich mehr daran interessiert, in der Theorie und Design Winkel als in Details von bestimmten Systemen.)

Answer 1

Ich denke, das ist eine ziemlich gute Frage. Obwohl RDBMS-Anbieter alle leicht unterschiedliche Implementierungen haben, ist die zugrundeliegende Theorie die gleiche und ich bezweifle, dass jemand B-Tree-Implementierungen als bestimmenden Faktor bei der Auswahl eines Anbieters verwendet.

Wie ich es verstehe, enthält die grundlegende Struktur jeder B-Baum-Seite Schlüssel und Zeiger. Die Zeiger verweisen kontinuierlich auf andere Seiten, die mehr Schlüssel und Zeiger enthalten, wobei der letzte Zeiger auf den zugehörigen Datensatz verweist.

Die Handhabung von Schlüsseln variabler Länge ist interessant. Vielleicht können andere die herstellerspezifischen Lösungen beleuchten.

Answer 2

Ich weiß, dass SQL Server eine Schlüssellänge von bis zu 900 Byte bei einer Seitengröße von 8192 Bytes haben kann. Wenn Sie tatsächlich 900 Byte Schlüssel haben, passen nur 9 (oder 8) Zeilen auf die Seiten eines Zwischenspeichers auf einem Index. Das bedeutet nur, dass der Verzweigungsfaktor niedriger als üblich ist. Dies könnte die theoretische B-Baum-Invariante verletzen, aber dies ist nur ein akademisches Anliegen, das die Leistung nicht signifikant beeinträchtigt. Es verändert die asymptotische Komplexität der beteiligten Algorithmen nicht.

Kurz gesagt: Dies ist ein rein akademisches Anliegen.