Zeiger Wettrennen

[Rolf B]

Hallo pl,

In meiner Datei liegen diese Tupel nach Schlüssel sortiert vor (...)

Diese Daten als B-Tree abzulegen macht keinen Sinn (...)

Du siehst den Widerspruch? Eine nach Schlüssel sortierte Menge lässt sich IMMER als Baum organisieren. Auch als B-Tree. Ein B-Tree wird in Seiten aufgeteilt; eine Seite enthält 1-N Einträge. Es gibt 3 Varianten:

1. Schlüssel und Daten haben feste Länge: Prima. Organisiere die Einträge der Seite als Array und suche binär darin
2. Schlüssel haben feste Länge, Daten nicht. Ok. Organisiere die Schlüssel als Array und füge jedem Schlüssel einen Offset auf seine Daten hinzu. Diese lege hinter dem Schlüsselarray ab. Da eine Page typischerweise kleiner als 64K ist, reicht für den Offset ein short-Wert.
3. Schlüssel und Daten haben variable Länge. Der blödeste Fall. Die Seiten müssen sequenziell durchsucht werden. Wenn die Schlüssellänge nicht zu breit variiert, könnte man die Schlüssel auf gleiche Länge auffüllen und auf Fall 2 zurückfallen.

Es ist aber nicht unbedingt einfach , einen B-Tree selbst zu programmieren. Wenn es ein readonly-Tree ist, wie vermutlich hier, geht's noch.

Denn die Performance ist auch ohne Optimierung schon so überwältigend, daß ich über Optimierungen nur nachdenke wenn's mir langweilig wird

Ach so. Dann können wir das hier ja zumachen.

Fazit jedenfalls: Ein Zeigerwettrennen bringt nur was wenn sie auf verschiedenen Kernen gleichzeitig rennen. Eine single-thread Optimierung setzt voraus, dass Du deine Datenstruktur für die gewünschte Abfrage optimierst. Angesichts des geringen Datenumfangs und der bereits angeführten Geschwindigkeit des Ist-Zustandes wird sich der Effekt für den Webseitennutzer nur bemerkbar machen, wenn Du deine Social Media Plattform "Ronald's Lounge"^[1] darauf betreiben willst.

Eine Alternative zu einem auf Disk gespeicherten B-Tree wäre übrigens, von CGI auf FastCGI zu wechseln. Dann kannst Du die Daten sortiert im RAM behalten und jede Suche binär durchführen. Das ist auch eine schöne Aufgabe für langweilige Abende 😂

Rolf

---

1. Ronald? ↩︎