# Optimizing Data Structures for Scalable System Architecture

**Podcast:** Engineering Kiosk
**Published:** 2026-06-23

## Transcript

Moin Moin und willkommen zu einer neuen Episode vom Engineering Kiosk Podcast.
Kurz und knackig, wir sprechen über Index und Datenstrukturen, denn die machen oft den Unterschied zwischen läuft schon und warum skaliert das hier eigentlich nicht?
Wir schauen uns an, was Red Black Trees sind und wie diese in Nginx für Timeouts genutzt werden, weshalb B und B Plus Bäume in Datenbanken so wichtig sind, wo Hash-Indizes glänzen und wo sie eben auch nicht helfen.
Außerdem gehen wir in die Richtung Try, Redix-Tree, Bitmap-Index und Bloom-Filter und auch wie klassische HTTP-Router und Git diese implementieren.
Los geht's, viel Spaß.
Aus so einer Podcast-Episode kriegt man relativ viele Daten raus.
Und ein Datenpunkt, den wir immer automatisch mitgenerieren, ist der Redeanteil von Wolfgang und mir.
Und oft kommt dann raus, dass ich mehr quatsche.
Warum, weiß ich jetzt auch nicht.
Aber damit ich diese Zahl verteidige, hole ich jetzt mal ein bisschen aus.
warum dieses Thema für heute relevant ist.
Wolfgang, bist du bereit?
Ich bin bereit und lausche dir gerne.
Warum du übrigens immer mehr Redeanteil hast, das ist, glaube ich, selbsterklärend.
Das braucht niemand erklären, aber ich lasse das mal als, wie man im Englischen sagt, Homework für unsere Listeners.
Kennst du das?
Hier ist ein langer Brief.
Ich entschuldige mich jetzt schon, ich hatte keine Zeit, einen kurzen zu schreiben.
Willst du dir jetzt rausreden?
Achso, nein, das ist negativ für dich.
Mach nur weiter.
Ich sage ja, ich hatte keine Zeit, mich kurz zu fassen.
Wie dem auch sein, fangen wir mit dem Thema an.
Und zwar war...
Vor kurzem das Engineering Kiosk Meetup Rhein-Ruhr.
Wer in der Gegend wohnt, im Pott Düsseldorf, Köln und so weiter, kann da gerne mal vorbeischauen, die nächsten Editions.
Wunderschöne Gegend.
Wunderschöne Gegend.
So, auf jeden Fall war das Meetup in Duisburg bei Kranke.com.
Und da ist ein Typ, der steht voll auf Retro-Computing und der hatte auf dem Meetup, das wusste ich gar nicht, ganz viel alte Computer da stehen.
So ein Commodore und so ein Amiga und ich glaube da war auch eine Playstation 1 noch dabei.
Ich wusste gar nicht, dass eine Playstation 1 schon zu Retro-Computing kommt.
Wie dem auch sei.
Ein bisschen mit dem gequatscht und dann sagt er, dass es eine riesen Retro-Computing-Szene gibt und dass heute noch neue Spiele für ein C64 und so weiter rauskamen.
Und dann fing er an zu erzählen, dass er die Dinge auch repariert und dass natürlich dann nicht nur immer die alte Hardware eingebaut wird, sondern dann auch neue Hardware.
Stell dir mal vor, du hast einen alten Porsche und du willst neue Lichter haben, dann kannst du natürlich die originalen Lichter einbauen oder du kannst moderne LED-Scheinwerfer einbauen.
Also das verändert ja schon ein bisschen den Porsche.
Auf jeden Fall hat er dann von so Hex erzählt, ja, du hast dann irgendwie eine alte Grafikkarte und einen alten Prozessor und dann hast du eine neue Grafikkarte daneben, die nur fürs Bildrendering genutzt wird.
Und wenn du dann irgendwie einen Ordner auf dem Computer aufmachen möchtest, dann nutzt du halt die alte Zippchen.
So weit, so gut.
Und das...
immer noch Spiele für diese alten Rechner rauskommen, hat mich verwundert.
Und das hat mich wiederum an unsere Doom-Folge erinnert, weil das Spiel Doom ist ja bekannt dafür, revolutionär gewesen zu sein in Bezug auf die Algorithmen, das Grafikrenderen unter dem Kontext der, ich sag mal heutzutage, langsamen Hardware.
Und jetzt kommen wir zum Thema, wir sprechen mal über Datenstrukturen.
Und jetzt fragt sich jeder, wieso hängt die ganze Sache zusammen?
Du musst intelligente Datenstrukturen haben, um schnelles Processing unter anderem auf alter Hardware laufen zu lassen.
Doom war da super fürs Rendering.
Wir erinnern uns, Binary Space Partitioning.
Wer da nochmal reinholen möchte, Episode 146.
Das heißt, jetzt wo wir neue Computer haben, neue Architekturen, brauchen wir eigentlich eh nichts mehr machen.
Das ist alles richtig, theoretisch oder in sehr vielen Fällen.
macht man den dritten Teil von Make it Work, Make it Beautiful, Make it Fast eigentlich nicht mehr, weil die Hardware schon fast genug ist.
Es kommt aber immer wieder vor, denn eine Sache, und Leute, die uns schon sehr lange hören, wissen, dass ich das schon mehrfach erwähnt habe, eine Sache, die ich konstant in meiner Karriere höre, mindestens einmal im Jahr, ist, du arbeitest an irgendeinem Software-System, es bricht unter Last zusammen, oder du hast ein hohes Datenvolumen, ganz viele Daten und deine Lese.
Operationen werden langsamer oder so weiter.
Dann kommt irgendwer, sagt, das skaliert nicht.
Was macht der klassische Junior- oder Mid-Level-Engineer?
Der geht nach Hacker News, sagt, MySQL skaliert nicht und kommt dann mit.
Was ist das heutige MongoDB?
Hast du gerade geglaubt, irgendwas ist kaputt?
Ja, siehst du, so geht es mir auch oft.
Und dann brauche ich unbedingt einen Kaffee.
Oder wie der Andi sagen würde, einen Kaffee.
Und für diese Koffeinenergie die ihr uns durch diese Kaffeespenden bereitstellt und die es uns eigentlich erst ermöglichen, diese Episoden zu produzieren, möchten wir uns einmal bedanken.
Und zwar bei den letzten Spendern.
Daniel, Jakob, Peter, Alfred, Florian, Michel, Dimo, David, Lukas, Adrian, Nico, Matthias, Wolfgang, by the way, schöner Name, Elias, Björn, Franco, Dominik, Paul und Fabian.
Und egal, ob ihr uns einen Kaffee sponsert oder vielleicht sogar ein Kaffee-Abo wie der Fabian oder einen ganzen Monatsbedarf an Kaffee wie der David, wir schätzen jeden einzelnen Kaffee und freuen uns wirklich über dieses ganze Koffein-Feedback.
Vielen Dank von Andi und von mir und jetzt geht es auch schon wieder zurück zur Episode.
Weil es macht auch Facebook nice, es ist auch zu alt fast.
Naja, kommt dann auf jeden Fall mit einer anderen Software und sagt dann, wir müssen Software A mit Software B austauschen.
Was ich mir immer denke, wenn ich sowas lese, ist, du tauscht ein bekanntes Problemset A durch ein unbekanntes Problemset B, denn die Root Cause ist sehr, sehr oft Datenstruktur.
Und was meine ich damit?
Verhältnis von Lesen und Schreibzugriffen, wie teuer ist ein Lesevorgang, beziehungsweise wie teuer ist ein Schreib...
Schreibvorgang.
Das dümmste Beispiel, was ich mir jetzt gerade ausgedacht habe, um die ganze Sache einfach mal zu verbildlichen, ist, bei einem Schreibvorgang in eine sortierte Liste muss die Liste immer neu sortiert werden, weil man beim Schreiben des Wertes nicht die richtige Stelle in der Liste kennt.
Das wäre zum Beispiel ein langsamer Schreibvorgang und wenn man das sehr oft macht, dann zieht man die ganze Applikation unter.
Leute, die uns sehr, sehr lange hören, die wissen, dass das kein neues Thema bei uns ist.
Ich meine, im Juli 2022, das war vor knapp vier Jahren, haben wir eine Episode über die Landau-Notation gemacht.
Die Landau-Notation, wir erinnern uns, ist die Big-O-Notation.
Das ist die Komplexität von Algorithmen.
Und da haben wir uns die Frage gestellt, ist das im Entwickleralltag relevant?
Und ich sage, ja, verdammt, es ist relevant.
Deswegen habe ich mir heute nochmal den Wolfgang geschnappt.
Der Wolfgang hat ja einen Doktor in Datenbanken, soviel ich weiß.
Datenbanken sind ja unter anderem bekannt für ganz viele smarte Indexstrukturen, aber sie kommen natürlich nicht nur in Datenbanken vor und deswegen gehen wir heute mal, ich sag mal so als zweite Episode zu den Performance Basics, die wir in Episode 269 gemacht haben, schauen uns nochmal ein paar Indexstrukturen an mit praktischen Beispielen.
Wo wird der Kram eigentlich verwendet?
Wie könnt ihr das eigentlich verwenden?
Und das ist nicht alles Overengineering, denn wenn ihr auch schon mal den Spruch gehört habt, das skaliert nicht, dann hört genau zu.
Denn oft ist eine gute Indexstruktur kein Gebrutsche, sondern hilft euch, das Problem zu lösen.
Jetzt bin ich mit der Intro fertig.
Ich habe ein bisschen ausgeholt, um meinen Räderanteil nach oben zu schrauben.
In dem Fall, wenn jemand sagt, das skaliert nicht, würde ich ja sogar argumentieren, wenn man dann sagt, okay, ich steige auf was anderes um, auf eine andere Indexstruktur, auf eine andere Library, die eine andere Indexstruktur hat, dann macht das ja vielleicht sogar Sinn.
Ob man gleich ein ganzes Datenbanksystem auswechseln muss, ist dann nochmal eine andere Sache.
Wir sprechen ja heute auch viel über den Hauptspeicher und da kann man natürlich vielleicht eine Implementierung durchaus schneller austauschen und da macht es natürlich auch Sinn.
Und es hilft dann in diesem Zusammenhang natürlich auch ein paar Indexstrukturen zu verstehen, grundsätzliche Herangehensweisen, was es denn an Indexstrukturen so da draußen gibt.
Und da werden wir heute ja auch ein paar machen, die über den klassischen B-Baum hinausgehen.
Aber vielleicht, weil du die letzte Episode erwähnt hast, die wir zu dem ganzen Thema gemacht haben.
Die Episode 269, wo wir ja vor allem über so Grundlagen gesprochen haben, was ist eigentlich ein Index, was macht das aus?
Ein Index ist ein Vertrag aus Datenstrukturen, wie du schon richtig gesagt hast, die braucht die richtige Datenstruktur.
Ich brauche irgendeinen coolen Algorithmus, möglichst niedriges O, also O von 1 ist natürlich das Coolste, kann direkt darauf zugreifen.
Ich muss die Hardware mit einbeziehen, also deine Playstation 1 und Andi, ja, du bist schon so alt.
Was kann meine Hardware?
Und heutzutage kann die Hardware natürlich viel, viel mehr.
SIMD und paralleles Processing natürlich, die verschiedenen Cache-Layer, das muss man alles mitdenken.
Und das Allerwichtigste, und das ist ja, was du auch immer predigst von deiner Kanzel da oben, von deiner Developer-Kanzel, was ist der Workload?
Was suchen wir eigentlich?
Weil es ist ein Unterschied, will ich eine ID immer rausholen aus meiner Datenbank oder aus meinem Index?
Oder brauche ich eine Range-Query?
Will ich alle Werte zwischen...
3,4 und 3,8 und das sind aber Millionen von Werten.
Also welche Anfragen habe ich, was speichere ich eigentlich ab und nur wenn ich dieses Quadrat, nenne ich es mal, also diese vier Punkte, Datenstrukturen, Algorithmus, Hardware und Workload verstehe, nur dann kann ich sinnvoll agieren und dann kann ich auch entscheiden, brauche ich eine neue Datenbank, skaliert das nicht oder habe ich halt vielleicht nur einen Punkt angeschaut von dem Ganzen und habe auf die Hardware geschaut und es skaliert halt für diese spezielle Hardware nicht.
Wobei ich aber auch sagen muss, zerdenkt die ganze Sache nicht.
Baut das einfach mal, schmeißt das mal auf Produktion, schaut, wie sich das verhält und habt halt Sichtbarkeit drauf.
Das bedeutet vielleicht ein paar Metriken, ein paar Perzentile über Request-Zeiten, Datenbank-Zeiten und so weiter.
Und da sieht man relativ schnell ein paar Ausreißer oder nicht.
Aber zerdenkt die ganze Sache nicht immer direkt von Anfang an.
Meines Erachtens nach, besonders heute in diesem KI-Zeitalter.
Baut lieber mal richtig schnell einen dreckig geweib codeten Prototyp.
Evaluiert das.
Schön machen kann man immer noch, gar keine Frage.
Aber habt nicht gar kein Verständnis von euren Datenstrukturen und von Lese-Schreibpatterns.
Denn wenn man meines Erachtens nach das versteht, kann man solche Applikationen einfacher machen.
Und was meine ich damit?
Man kann den ganzen Cache-Layer entfernen.
Denn Caching ist immer ein Problem.
Cache-Invalidation.
Ihr habt immer Bugs und so weiter und so fort.
Und ich weiß, viele Leute sagen, man wird nicht bezahlt für Simplifizierung des Stacks.
Die Leute, die On-Call sind, und das bist du hoffentlich selbst für deinen Stack, werden dir wahrscheinlich danken.
Ich möchte gar nicht zu sehr in dieses KI-Thema jetzt eintauchen, aber du hast gerade zwei gute Punkte gesagt.
AI-Generated-Code kann nämlich genau in diese zwei Kerben schlagen.
Einerseits kann er von Anfang an schon sehr gut optimiert sein.
Ich hatte gerade vor zwei Tagen eine SQL-Query.
Da bin ich echt lang drüber gesessen und habe gedacht, what the fuck, was passiert da?
Und sie war aber korrekt und sie war verdammt intelligent und verdammt gut gemacht.
Habe mir gedacht, okay, cool und ich mache echt viel mit SQL.
Aber auf der anderen Seite hat man dann wieder so Dinge, dass es absolut zugemüllt ist und wahnsinnig kompliziert irgendwas gemacht wurde, wo man dann vielleicht manuell eingreifen muss.
Also es gibt durchaus beide Varianten und darum ist es gut, auch da mal einen Blick drauf zu werfen und Metriken zu haben.
Und wie du richtig gesagt hast, Es macht keinen Sinn, da premature Optimization zu machen, aber wenn man saubere Metriken hat, dann findet man vielleicht auch schnell raus, okay, was ist denn bei mir langsam?
Und wenn ich dann eine spezielle Funktion habe, zum Beispiel, die langsam ist, dann kann ich da eintauchen und meistens kann ich da so viel Zeit wieder rausholen mit der einen Optimierung, dass mein ganzes System um 90 Prozent vielleicht schneller wurde.
Und da macht es dann natürlich auch Sinn, die Zeit zu investieren in diesen kleinen Teil, aber nicht überall automatisch immer alles mitdenken und im Vorhinein schon mitdenken, sondern im Nachhinein gezielt reagieren, da, wo es Probleme gibt, 80-20-Regel, da tauche ich dann tief ein.
Ich meine, das Geile jetzt, was du in dieser Episode auch lernen wirst und dann hoffentlich auch anwenden kannst, ist ja, Wenn ich sage, gewiped coded, meine ich nicht, mach was schnell, liebe KI, sondern du hörst diese Episode, sagst du mal, pass mal auf, Anni und Wolfgang, die haben doch über so ein Reddix-Tree gesprochen.
Wäre das vielleicht was?
Okay, schmeiß dann Claude oder irgendwie deinen OpenCode oder was du auch immer nutzt, halt einfach mal auf deine Daten und sag, pass mal auf, schau dir mal die Daten an.
Ich möchte das in dieser Form lesen.
Wäre ein Reddix-Tree hier sinnvoll?
Lass die KI einfach mal denken.
Das ist ja, dass du die KI eigentlich mit den richtigen...
Quellen-Promps und dann einfach die verschiedenen Indexstrukturen vielleicht einmal durchdenkst, mal vergleichen lässt, vielleicht sogar einen Benchmark von der KI eben bauen lässt, nur um ein Gefühl zu kriegen.
Da bist du wahrscheinlich schon in einer halben Stunde, dreiviertel Stunde relativ weit und kannst es einschätzen, ob zum Beispiel eine Indexstruktur hilft oder nicht.
Wer aber jetzt sagt Indexstruktur, ich habe keine Ahnung, wovon ihr reden, warum das alles so richtig ist, hört euch mal ganz kurz die Episode 269 nochmal an oder wenn ihr es noch gar nicht getan habt, hört ihr euch sie einfach an.
Da haben wir relativ viele Basics gemacht, so die Write-Amplifications, diese vier sichtweisen Datenstruktur, Algorithmus, Hardware, Workload und so weiter, das, was der Wolfgang erzählt hat.
Aber lass uns mal ganz kurz in die verschiedenen Kategorien der Indexstrukturen einsteigen.
Wie ich damals studiert habe, in den 2000er Jahren, also sehr am Anfang von den 2000er Jahren, da hat es immer geheißen, ja, RAM ist schnell, Festplatte ist langsam.
Also brauchen wir spezielle Indexstrukturen für den RAM und für die Festplatte.
Das war so die Hauptkategorisierung, die wir eigentlich damals hatten.
weil es eben so starke Unterschiede gegeben hat.
Die Festplatte hat sich gedreht.
Also für alle, die das nicht mehr wissen, das war früher kein Solid-State-Speicher, sondern wirklich so klassische Spinning-Disks.
Und der RAM war halt das Schnelle, wo man so gesagt hat, da hat man Random Access Memory.
Also man kann überall schnell zugreifen.
Jetzt, wie wir alle wissen, hat sich das stark geändert.
Mittlerweile haben wir superschnelle Festplatten, die eigentlich sehr nahe an dem RAM dran sind.
Wir haben auf der CPU-Seite mittlerweile teilweise Vier Cache Layer, L1 bis L4.
Es gibt hunderte Optimierungsvarianten, also SIMD zum Beispiel, dass man mehrere Operationen parallel machen kann auf seinem Speicher oder auf dem Register eigentlich.
Man hat Optimierungen, Branch Predictions, ähnliche Dinge am CPU.
Also es ist super, super kompliziert geworden.
Das heißt, von den vier Punkten ist diese Hardware-Seite eigentlich wesentlich komplexer geworden.
Und heute kann man viel mehr eigentlich mit der Hardware machen.
und viel mehr optimieren auf eine spezielle Hardware.
Auf der anderen Seite ist eben die Festplatte so mit dem Rahmen ziemlich zusammengewachsen und heute muss man eigentlich genau drauf schauen, was habe ich für Hardware eigentlich zur Verfügung, in welchem Bereich von dieser Hardware mache ich meine Berechnungen.
Sind es große Datenmengen, dann werde ich trotzdem auf der Festplatte sein.
Es gibt immer noch Dinge, die auf der Festplatte gelten, die im Rahmen nicht gelten.
Das heißt, ich habe schon Unterschiede an sich, aber es geht mehr darum, Wie groß sind meine Datenmengen?
Wo speichere ich die ab?
Wo wird berechnet?
Durch welche Layer muss ich durch?
Muss ich das von der Festplatte bis in das Register bringen?
Habe ich was im RAM gespeichert?
Wie funktioniert das mit dem persistenten Speicher?
Also solche Dinge muss ich mir überlegen und darauf bauend kann ich dann entscheiden, was ich für Indexstruktur verwende.
Früher war es easy, binär, Baum hat mit dem Hauptspeicher, B-Baum, Sekundärspeicher und die Sache hat sich erledigt.
Da hat man dann schon 90% der Fälle eigentlich abgedeckt gehabt.
Weiß ich übrigens, mehr interessiert für das ganze Cache-Thema.
Wir haben eine Episode, der Andi hat es mir in die Vorbereitungsnotizen geschrieben, Episode 73.
Ich kann mich ehrlich gesagt persönlich gar nicht mehr daran erinnern, aber scheinbar haben wir eine Episode gemacht über Caches, CPU, Ersetzungsstrategien, Invalidierung und wie das alles im Inneren funktioniert.
Aber es sei mir verziehen, wenn man über 250 Episoden hat.
dass man auch mal die eine oder andere vergisst.
Vielen lieben Dank, Opa, dass du mal wieder vom Krieg erzählt hast mit diesem RAM und mit diesem Spinning-Disc und so weiter.
Ja, und von der Episode 73, aber die hast du mir da reingelegt.
Ja, irgendwer muss ja diese Hausaufgaben hier machen.
Jetzt hast du gesagt, früher war die Frage RAM oder Disc.
Ist die Frage noch existent?
Wurde die Frage ersetzt oder ist die Frage einfach weggefallen?
Also ich habe es ja schon ein bisschen angedeutet.
Es geht im Prinzip darum, wo läuft mein Algorithmus, die Hardware und wie viel...
Daten habe ich natürlich, Zugriffsmuster und so weiter natürlich auch.
Aber das sind so zwei Kernkomponenten, die einen großen Einfluss auf den Auswahlprozess haben.
Wir haben immer noch ganz klassisch Bäume als Indexstrukturen.
Also fast alle Indexstrukturen sind Bäume, weil die eignen sich sehr gut als Indexstruktur, weil sie eine Komplexität haben von, Andi, O von?
Logarithmisch und dann kommt es, ja gut, ja doch, dann kommt es auf die Teilimitierung, von welchem Baum wir sprechen und so weiter an.
Aber ich würde sagen...
Wir fangen erstmal bei logarithmisch an, was schon mal ganz gut ist.
Ich habe die Frage mal in einem Google-Bewerbungsprozess übrigens gehabt, bei dem ganz anfänglichen Test.
Und logarithmisch ist richtig, Andi.
Also du wärst schon einen Sprung weiter.
Bäume sind immer logarithmisch, genau weil man bei jedem Knoten zwischendrin sich aufsplittet, um das 100-fache, 200-fache, beim Binärbaum nur das Doppelte, aber auch das ist logarithmisch, weil man den Suchraum eben immer teilt.
Im Idealfall mit einem möglichst hohen Faktor teilt.
Es gibt natürlich schon irgendwelche Indexstrukturen wie Bitmaps, Blumenfilter, da kommen wir auch noch später drauf zu sprechen, aber die Hauptkategorie sind sicher Bäume.
Und dann ist die Frage, wie optimiere ich den Baum auf meine Speicherstruktur?
Das heißt, im RAM oder in meinen Caches habe ich unterschiedliche Größen und üblicherweise optimiert man den Baum auf dieses Zugriffsmuster im L1-Cache, L2-Cache, im Register, auf der Festplatte, je nachdem, wie viel ich gleichzeitig laden kann.
Wir haben das ja auch bereits öfter schon besprochen.
Die CPU versucht eigentlich mit dir mitzudenken und macht sogenanntes Prefetching.
Das heißt, es werden schon Daten vorgeladen, beziehungsweise du musst teilweise die Daten einfach, die rundherum liegen von diesem Datensatz, den du eigentlich haben willst, die musst du einfach immer mitfetchen, weil man kann halt keinen einzelnen Integer auf einer Festplatte lesen, sondern nur immer eine ganze Seite, üblicherweise, die in der Memory geladen wird.
Das heißt, es wird Prefetching betrieben, es wird etwas mitgeschickt und wenn der Index dieses würde ich es mal nennen, mitdenkt, dann kann er natürlich davon profitieren.
Und Bäume optimieren genau ihre Größe, also wird es doppelt aufgesplittet, 200-fach aufgesplittet pro Ast, wird dementsprechend auf die Größe von den Caches, von der Festplatte, von der Page dementsprechend optimiert.
Und das ist eigentlich die Hauptoptimierung, die man mit so Bäumen machen kann.
Und dann unterscheiden sie sich gar nicht mehr so viel, egal ob das auf der Festplatte ist, im RAM oder vielleicht sonstige Optimierungen noch für, die Cash-Layer zum Beispiel, obendrauf kommen.
Aber eine Frage hast du mir noch nicht beantwortet.
Wenn ich in einem Baum von der Wurzel parallel einen Fan-Out mache auf all meine Kindsknoten auf dem ersten Level und wir haben gesagt, es ist eine logarithmische Komplexität, ist es dann nicht besser, sehr viele Knoten auf dem ersten Level zu haben, weil dann der Algorithmus im Endresultat schneller wird, weil ich eine geringere Tiefe habe im Baum?
Also warum gibt es verschiedene Implementierungen, wie man den Fanout von der Wurzelknoten macht?
Warum gibt es da nicht einen Standard?
Also üblicherweise hat man denselben Fanout.
Du hast vom Rootknoten 200 Kindsknoten und bei jedem Kindsknoten wieder 200 Kindsknoten.
Darum hat man da einen Lockdown von Basis 200 zum Beispiel und du hast da bei einem klassischen B-Baum, der jetzt in der normalen Datenbank verwendet wird, wenn du einen Fanout von 200 hast, was üblich ist.
dann hast du auf der Ebene 3 schon 8 Millionen Notes Platz.
Das heißt, du musst nur drei Schritte springen, um 8 Millionen Einträge überhaupt abzubilden in deinem Baum.
Darum ist das ja so effizient.
Jetzt deine Frage, warum gibt es da überhaupt unterschiedliche Verzweigungsgrößen?
Und vor allem, wenn man ja denkt an den B-Baum, sorry, jetzt bin ich auch schon verwirrt, der Binärbaum, B-Baum und Binärbaum ist ja immer sehr verwirrend.
Der Binärbaum im Hauptspeicher hat ja nur zwei Kindsknoten.
Jetzt wäre die Frage immer, warum habe ich überhaupt so eine unter Anführungszeichen schlechte Indexstruktur für den Hauptspeicher?
Die Argumentation war natürlich früher, ich kann schnell springen in meinem Speicher, aber ich habe natürlich auch dort Cashlines, die eine gewisse Größe haben.
Und das verwenden viele Indexstrukturen mittlerweile, also dass man da auch im Hauptspeicher nicht nur zwei Kindsknoten hat, sondern eben auch mehrere, angepasst auf die Cashlines.
Aber man muss immer mitdenken, dass da ein Trade-Off dahinter steckt.
Weil das Ändern, das Löschen, das Hinzufügen, das kostet alles viel mehr Zeit, wenn du so eine komplexe Indexstruktur hast, wo du eben eine Fanart von 200 hast.
Im Vergleich zu einem Binärbaum, wo man ganz einfach einhängen kann.
Superschnelle Operation.
Wenn ich jetzt im Hauptspeicher ganz viele Inserts habe, Updates, Änderungen in meiner Datenstruktur, dann macht es natürlich Sinn, da ein Trade-Off zu finden zwischen Komplexität meiner Indexstruktur und der Zeit, die ich benötige, mit der Inrichtsstruktur zu arbeiten.
Und daher gibt es auch immer noch Use Cases, die den Binärbaum wirklich im Hauptspeicher verwenden.
Wobei man dazu sagen muss, der klassische Binärbaum wird eigentlich kaum mehr verwendet, weil der nicht balanciert ist.
Und das Übliche, was so verwendet wird, sind Red-Black-Trees, AVL-Trees.
Das sind so die bisschen besseren Binärbäume, die balanciert sind.
Ein paar Vorteile haben dieser Red-Black-Tree, da wird dann jeder Knoten...
und der roter Knoten darf keinen roten Kindsknoten haben.
Also da wird einfach der Algorithmus noch ein bisschen optimiert, damit es besser funktioniert.
Und das sind eigentlich heutzutage so die klassischen Implementierungen von einer Tree Map in Java oder Map in C++.
Da steckt im Hintergrund eigentlich immer so ein ganz einfacher, ich nenne es mal Binärbaum, dahinter, weil der einfach super einfach ist, im Normalfall schnell funktioniert und für die meisten Use Cases eigentlich ausreicht.
Den Red Black Tree, den habe ich auch noch in Erinnerung, weil ich finde den, wie soll ich sagen, so prägnant vom Namen her.
Das ist so die einzige Datenstruktur, die mit Farben in Verbindung steht.
Und deswegen habe ich den schon irgendwie, ist der irgendwie hängen geblieben aus dem Studium.
Lass uns da doch mal reinspringen.
Lass doch mal wirklich gucken, okay, warum ist das Ding so knurker?
Lässt sich mit einem Satz beantworten.
Der Trade-off zwischen Komplexität und Geschwindigkeit.
Er ist relativ schnell im Hauptspeicher und super einfach zu implementieren, ist zusätzlich noch balanciert.
Also balanciert heißt, dass der Baum nicht in eine Richtung hängt, weil nur ein ausgeglichener Baum ermöglicht, dass du schnell Elemente findest.
Weil stell dir mal einen Baum vor, der bei der Wurzel anfängt, links einen Knoten hat, einen Subknoten und eine Million Knoten hängen irgendwo rechts dran.
dann kann es im Worst Case sein, dass du eine Million Knoten durchwandern musst, um ein Element zu finden, weil der eben so rechtslastig ist und darunter hängt komplett auf der rechten Seite.
Darum versucht man immer einen balancierten Baum zu machen, der ausgeglichen ist zwischen links und rechts von den Kinderknoten, damit man eben da dementsprechend auch schnell suchen kann.
Der Nachteil an so balancierten Bäumen ist natürlich, dass sie balanciert werden müssen.
Das heißt, wenn du irgendwie ein Ungleichgewicht hast, dann musst du diesen kompletten Baum...
adaptieren, umändern, Knoten umhängen und das kostet dann dementsprechend auch wieder.
Und da verhält sich der Red-Black-Tree eigentlich im Trade-Off sehr gut und wird darum so als Standardimplementierung verwendet für alles, was irgendwie sortiert sein muss.
Zur Vorbereitung dieser Episode habe ich mir gedacht, okay, der Wolfgang kommt wieder mit seinem Doktorwissen um die Ecke von irgendwelchen Professoren mit irgendwelchen Slides.
Er klärt mir einen von Trade-Off.
Und am Ende habe ich immer noch keine Ahnung.
wo ich das implementiere.
Deswegen habe ich mir einfach mal einen realen, praktischen Use Case rausgesucht.
Der Web-Server Nginx implementiert nämlich auch den Red-Black-Tree.
Und zwar, nur mal ganz kurz, Nginx selbst ist, beziehungsweise läuft in einem großen Event-Loop.
Er kriegt natürlich Connections rein, oder HTTP-Connections.
Und eigentlich hat jede Connection ja einen Read-Event und einen Write-Event.
Also man liest die Connection und Nginx macht dann irgendwas oder der Upstream-Proxy macht dann irgendwas und dann wird irgendwas auf die Connection wieder geschrieben.
Und jedes dieser Schreib- oder Lese-Events hat selbst oder ist selbst ein Red-Black-Tree-Knoten mit verschiedenen Timeouts und Unterknoten.
Denn all diese Timeouts, Client-Timeout, Server-Timeout, TLS-Timeout, Upstream-Proxy-Timeouts und so weiter und so fort, die müssen ja gemanagt werden, da muss drauf reagiert werden, da teilweise muss was blockiert werden, wenn man auf irgendwas wartet und so weiter und so fort.
All diese Timeouts werden in Red-Black-Tree selbst gemanagt.
Somit kann man eigentlich sagen, dass der Red-Black-Tree selbst bei NGX so ein bunt gemischter Haufen von allen offenen Deadlines, von allen Verbindungen, von allen Read-Write-Events und so weiter des einzelnen NGX-Workers sind.
Dann kannst du sagen, okay, der linkeste Knoten ist immer die nächstfällige Deadline und umso weiter du nur nach rechts gehst, erhöht sich das Delta zwischen dem nächsten...
Timeout und so weiter und so fort.
Und da sieht man schon, dass es ein perfekter Use Case ist, weil du hast ganz viele Connections üblicherweise bei NGINX, also tausende, hunderttausende Connections dann multipliziert mit den Timeouts.
Also sehr viel, was sich auch schnell ändert, weil Connections sind ja meistens nicht so langlebig, man muss warten, also es ist extrem viel Traffic, Write, Last auf diesem Baum und er muss sortiert sein.
Und da eignet sich dann natürlich genau so ein Hauptspeicher, Index, perfekt.
Wenn man das Ganze jetzt auf der klassischen Sekundärspeicher-Seite betrachtet, da gibt es natürlich den klassischen B-Baum, den man auch so immer lernt, wenn man irgendwann mal Datenbanken studiert oder so.
Der B-Baum ist so der Klassiker, wird auch immer und überall noch verwendet, wobei man ja genau sagen muss, das ist auch kein klassischer B-Baum mehr, sondern ein B-Plus-Baum oder es gibt ein...
Cache-Sensitive B plus 3 in CSB plus 3.
Das sind eher so die Dinge, die heutzutage verwendet werden, aber die basieren natürlich alle auf dem klassischen B-Baum.
Und wenn man Fanout von 2 hat im Hauptspeicher bei einem Binärbaum, dann hat man eben beim B-Baum einen sehr viel höheren Fanout pro Knoten.
Das heißt, man hat da üblicherweise 200 bis 400 Kinderknoten.
eben den Suchraum möglichst stark aufzuteilen.
Und dann hat man eben auch einen Logarithmus zu Basis 200 im Endeffekt und bekommt ganz viele Knoten pro Ebene unter.
Und darum ist der B-Baum eigentlich so stark.
B-Plus-Baum, ist das Plus dann die Enterprise-Version, für die ich dann mehr zahlen muss?
Oder wofür ist das Plus?
Ist Plus wirklich besser als der normale B-Baum?
Ja, es ist einfach eine Weiterentwicklung, der B-Plus-Baum und der B-Plus-Baum, der heutzutage eben Anwendung findet.
Ist eigentlich nur ein kleiner Unterschied.
Beim klassischen B-Baum werden die Einträge selbst, also die Zeilen von der Datenbank-Tabelle zum Beispiel, in den Knoten gespeichert.
Jetzt nehmen die natürlich viel Platz weg, wenn du da diese ganze Zeile reinspeicherst.
Was der B-Plus-Baum macht, ist, er legt die ganzen Daten separat in den Blättern, also ganz unten im Baum, ab, damit du in den Knoten nur das Feld hast, auf das dein Index basiert, also die ID zum Beispiel.
Du speicherst nur die ID, die...
Kunden Nummer zum Beispiel in den Knoten, aber wie der Kunde heißt, ist dann ganz am Ende in den Blättern gespeichert und so bekommst du noch mehr in einen Knoten unter und das ist ja die Idee, dass der Knoten möglichst deinen Suchraum separiert und dein Knoten sollte eigentlich so groß sein wie eine Festplattenseite, also dieser Block, der immer von der Festplatte geladen wird, egal wie viel du brauchst, du musst immer diese ganze Festplattenseite laden, jetzt probierst du deine Knoten genauso groß zu machen wie die Festplattenseite und das macht der B-Plus-Baum.
einfach noch mal effizienter.
Und darum wird er heute eigentlich überall eingesetzt.
Und der Cache-Sensitive B-Plus-Tree, also der CSB-Plus-Tree, den ich ganz am Anfang auch erwähnt habe, der passt sich jetzt ganz speziell auf die Cache-Größen noch mal an.
Das heißt, meine Knoten werden so gewählt, wie groß meine Cache-Line sind, weil der dann auch wirklich im Hauptspeicher.
Anwendung findet.
Also nicht nur auf der Festplatte, sondern auch in meinem Hauptspeicher und da sollte der Knoten dann genauso groß sein wie eine Cashline oder ein Vielfaches von einer Cashline, möglichst viele Elemente, die in irgendeiner Form zusammengehören, wie eine Kundennummer.
Da gibt es halt Blöcke, die zusammengehören.
Eine Kundennummer 11 sollte neben 10 liegen und nicht neben 3476.
Das heißt, man sortiert es richtig und probiert dann möglichst viel in eine Cashline reinzupacken.
Also auch dieser Klassiker, wo man sagt, der klassische B-Baum ist ja nicht geeignet für den Hauptspeicher, stimmt, aber mit einem Cash-Sensitive B-Plus-Tree zum Beispiel schon.
Und darum werden dann auch B-Bäume im Hauptspeicher durchaus angewendet.
Und heutzutage sind ja sehr viele Datenbanken überhaupt nur im Hauptspeicher, diese klassischen Hauptspeicherdatenbanken.
wie eine HANA zum Beispiel von SAP, die ja sehr früh damit begonnen haben.
Und die verwenden dann natürlich auch dementsprechend angepasste B-Bäume, die auf den Hauptspeicher optimiert sind.
Und das klingt immer so komplex, aber im Prinzip, die Hauptoptimierung liegt einfach in der Größe von so einem Knoten.
Weil der Rest wird dann von der Hardware gemacht.
Bäume, Bäume, Bäume, Bäume, Bäume.
Ich weiß, Wolfgang, kommst aus Innsbruck.
Du liebst die Berge, du liebst die Natur.
Ich komme aus dem Pott.
Wir haben eine ganze Menge Bäume inzwischen, aber wir lieben auch den Stahl.
Deswegen lass uns mal weg von der Natur.
Und zwar habe ich immer, wenn ich Bäume höre, komplexe Datenstrukturen im Sinn, komplexe Implementierungen im Sinn.
Und deswegen bin ich ja ein Freund der einfachen Sachen.
Immer wenn ich nämlich an Indexstrukturen denke, denke ich an den Hash-Index.
Wo verwendest du denn?
Naja, generell hat jede Programmiersprache ja irgendwie eine Art von, ich sag mal Hash-Map.
Sogar, ich meine, in PHP ist es ein Array, hatte ich, glaube ich, schon mal irgendwann erwähnt hier, wo du eigentlich ein Key und dann eine Struktur drunter hast.
Java wäre es dann eine Hash-Map, in Go wäre es ebenfalls eine Map.
Ich kenne den Typen gerade in Rust nicht, aber mich würde sehr wundern, wenn Rust keine Hash mehr hätte.
Genau, auch da wieder ganz easy, wird im Hauptspeicher ganz klassisch verwendet, gibt es in allen Programmiersprachen, gibt es auch in Datenbanken.
MySQL hatte immer einen Hash-Index, den man auch verwenden konnte, keine Ahnung, ob der deprecated ist.
In der Realität wird er kaum in Datenbanken eigentlich verwendet, weil er den großen Nachteil hat, dass dieses Ding eigentlich nur Punktabfragen gut behandeln kann.
Das heißt, ich habe eine ID, will genau diesen einen Kunden haben.
Kunden Nummer 5 und dann will ich die Daten haben.
Das heißt, ein Sprung im Hauptspeicher zu dem richtigen Datensatz, gib mir das Ganze.
Jetzt ganz klassisch in Datenbanken oder wenn man viele Daten processen will, dann will man ja meistens nicht nur einen Datensatz haben, sondern ich mache eine Range Query, gebe mir alle Kunden in Deutschland, die weiblich sind, die in einem gewissen Altersspektrum sind und da will ich irgendwas rausfinden.
Und für solche Anfragen sind Hash-Indizes einfach schlecht geeignet, weil das eben so ein klassischer Sprung ist.
Das Ganze basiert ja auf einer Hash-Funktion.
Das heißt, eine Funktion bekommt irgendeine Kundennummer zum Beispiel und im Hintergrund wird das dann gemappt auf eine Speicheradresse.
Die einfachste Form einer Implementierung, die man immer gern verwendet, ist Modulu.
Das heißt, ihr habt einen Speicherbereich von, keine Ahnung, 100 oder 200 Einträgen, die ihr Platz habt.
Dann mache ich eine Modulu-Funktion, Modulu 200, nehme die Kunden-ID, Modulo 200, weiß ich, wo ich das Ganze hinsetzen soll in meinem Speicher.
Wenn ich die Kundennummer 250 habe, Modulo 200, landet es beim Index 50.
That's it.
Super einfach.
Gibt es natürlich auch komplexere Hash-Funktionen.
Kann man teilweise auch selber festlegen, die Hash-Funktionen.
Aber super einfach, super schnell zu berechnen, weil diese Funktion Modulo-Berechnung ist super schnell.
Und ihr bekommt direkt die Speicheradresse.
Also ganz einfache Struktur, aber eben nur für Punktanfragen und keine Range-Queries und drum eher so im Hauptspeicher oder im klassischen Coding anzutreffen.
Ich meine, Modulu ist ein bekanntes Beispiel, das hat sich schon erwähnt.
MD5 auch sehr schnell, jetzt nicht für irgendwelche Passwörter zu nutzen, bitte, aber für so eine Hash-Map und so weiter eigentlich total super oder ein Short-MD5 mit 16 Characters anstatt 32.
Aber immer wenn...
Ich über Hashes spreche, kommen mir auch immer diese theoretisch oder vielleicht auch praktischen Angriffe von Hash-Kollisionen in den Sinn.
Wie geht denn so eine Hash-Map mit Hash-Kollisionen um?
Die Tücke liegt im Detail und besonders bei der Hash-Implementierung, weil klassischerweise heißt es ja immer, der Hash hat O von 1.
Weil du einen Eingabewert hast, eine Speicheradresse rausbekommst, O von 1.
Super gute Komplexität.
Sollte ja super schnell sein.
Da stellt sich übrigens auch die Frage, wenn das so schnell ist, Warum kann ich das nicht dann für eine Range Query machen?
Ich kann ja fünf IDs anfragen, aber ich muss das Ganze halt fünfmal ausführen.
Also rein von der O-Notation, fünfmal eins ist zwar immer noch konstanter Speed, aber in der Realität, wenn ich halt 5000 Mal eine Anfrage mache, die auch sehr schnell ist, Punktabfrage, ist es halt trotzdem 5000 Mal sehr schnell und das ist dann vielleicht schon wieder langsam.
Nur weil etwas O von eins ist, heißt das nicht, dass es für jeden Anwendungszweck funktioniert.
Und wie du sagst, das andere Problem ist, wenn meinen Speicherbereich, in dem ich eigentlich die Dinge ablege oder berechne mit meiner Hash-Funktion, wenn dieser wesentlich kleiner ist als die Anzahl der Elemente, die ich habe.
Oder meine Hash-Funktion einfach schlecht gewählt ist, dass sie ganz viele verschiedene Elemente immer auf denselben Speicherort legen will.
Weil dann bekomme ich diese Kollision und dann muss ich...
irgendwas mit dieser Kollision machen.
Üblicherweise gibt es da verkettete Listen, die da dran gehängt werden oder vielleicht eine Unterindex-Struktur, dass ich, wenn ich auf die gleiche Speicheradresse mappe, dass ich da dann in irgendeiner Form einen neuen Index dran hänge, in dem ich dann wieder suchen muss.
Aber das Problem besteht, dass im Worst Case bei der klassischen Implementierung natürlich sein kann, dass alle meine Elemente genau am selben Ort landen und ich dann einfach eine verkettete Liste dort habe.
Und ich muss durch 1000 Elemente durch, obwohl ich zuerst einen superschnellen Sprung habe.
Aber dort liegen halt 1000 Elemente und ich muss wieder durch alle 1000 Elemente durch.
Und da degradiert dann mein Speed natürlich extrem.
Und von dem muss ich mich immer fernhalten.
Darum sagt man so üblicherweise, eine Hash-Map sollte nur drei Viertel gefüllt sein.
Und man sollte die Größe dann dementsprechend adaptieren.
Meistens gibt es da auch einen Parameter, wenn man programmiert.
Ab wann soll die Hashmap vergrößert werden, der Speicherbereich dahinter?
Weil da muss ja alles umorganisiert werden.
Wenn ich jetzt ein Modulo habe zum Beispiel, muss das alles neu berechnet werden.
Wo liegen meine Elemente?
Kostet dementsprechend wieder Zeit.
Will ich natürlich verhindern.
Also da gibt es dann Unterschiede in der Implementierung.
Glücklicherweise, wenn man eine klassische Implementierung verwendet in der Programmiersprache der Wahl, dann wird es im Hintergrund meistens weg abstrahiert und gemanagt.
Aber wenn einmal eine Hashmap super langsam sein sollte, kann sowas durchaus der Grund sein.
Und immer wenn man die Hashmap selbst reorganisieren muss, wie der Wolfgang gerade gesagt hat, nennt man das Resizing, also vergrößern und so weiter oder halt auch verkleinern.
Beziehungsweise auch Rehashing, je nachdem, was man für eine Hashfunktion hat, dass man wirklich alle Speicher-Ode nochmal neu berechnen muss.
Also ich muss wirklich durch alle meine Elemente durchgehen, immer wieder in Hash bilden, schauen, hat sich der verändert, muss ich irgendwas umspeichern.
Super teuer natürlich.
Super teuer.
Vielleicht sogar Stop of the World für deine Applikation.
Vielleicht machst du es irgendeinen Background-Thread, aber dann ist der Zugriff auf diese Datenstruktur ja auch irgendwie gehindert.
Redis hat dafür eine sehr schöne Implementierung.
Und deswegen mag ich Redis ja.
Eine Episode ohne Redis will ich mal erleben.
Naja, Redis hat halt ein Detail implementiert, was im Lehrbuch oft erwähnt wird, aber in der Praxis oft fehlt.
Und zwar nennt sich das Incremental Rehashing.
Was die tun ist, unten drunter für jede Hashmap maintainen die eigentlich zwei Hashtabellen.
Und wenn die erste Hashtabelle, ich sag mal, dem Resizing unterzogen werden muss, dann würde das eigentlich so Stop of the World bedeuten, die wird neu berechnet und so weiter.
Was die eigentlich machen ist, immer wenn auf die Hashmap zugegriffen wird, also das bedeutet, wenn du ein Add oder ein Delete oder ein Find von deinem Element machst, dann verschieben die ein Element oder ein Bucket in die zweite Hashmap.
Das bedeutet, die ziehen das Resizing eigentlich über, die stretchen das.
Die stretchen das Resizing eigentlich über eine gewisse Zeit und sind dann natürlich nicht einmal ganz teuer, sondern kontinuierlich immer so ein bisschen teurer, also mit einem Minimal Overhead.
Und das finde ich natürlich schon eine sehr schöne Lösung, weil ich sag mal, das versucht die Trade-Offs irgendwie so ein bisschen zu glätten.
Einen anderen praktischen schönen Use-Case, den ich gefunden habe, ist, wo man eigentlich zum Beispiel eine Hash-Map einsetzen würde oder einen Hash-Index einsetzen würde, ist, stell dir vor, du hast ein Alerting-System, Der kriegt natürlich dauerhaft Alerts und soll dich dann anrufen oder pagen oder ähnliches.
Und ab und zu ist man ja zum Beispiel an einem Server am Arbeiten.
Das bedeutet, ich habe da jetzt irgendwie meine Datenbank und wir wissen, das Ops-Team macht da gerade Datenbank-Maintainance und da kann das mal sein, dass dann irgendwelche Alerts fliegen.
Deswegen hat meist jeder Alert-Manager oder jedes Alerting-Tool irgendwie so eine Funktion.
Mach diesen Alert mal leise, also silence den mal.
Und das ist natürlich perfekt für so eine...
für so einen Hash-Index.
Du hast dann den Alert-Namen, den packst du als Key in die Hash-Map und sagst als Value dann 1 zum Beispiel und wenn der Alert reinkommt in das Alerting-System, dann guckt das Alerting-System, habe ich diesen Alert in meiner zu silenzen Liste?
Wenn ja, dann verwerfe den Alert und feuer den nicht raus, page den Wolfgang nicht.
Das ist so zum Beispiel ein ganz einfacher Use-Case mit einer ganz klassischen Hashmap oder Hashindex.
Weißt du, was das Schöne ist an AI?
Man kann nebenbei, während du sprichst, mal so Sachen überprüfen lassen.
Ich habe es leider nicht hundertprozentig herausgefunden, ob Redis sehr früh dran war.
Sie waren zumindest nicht spät mit der Implementierung, aber das würde dich vielleicht noch mehr freuen.
So wie es aussieht, war das erst 2013 und Go hatte es schon 2012, Andi.
Und Java kam dann überhaupt erst 2014.
Ich habe jetzt nicht geguckt, woher das kommt.
Was ich aber weiß, ist, dass der Autor von Redis und auch die Köpfe hinter Go, Rob, Pike und Co.
natürlich sehr, sehr, sehr viel Paypal lesen.
Und dass auf der anderen Seite auch die Köpfe hinter Go sehr viel im Competitive Programming unterwegs waren.
unglaublich gute Fundamente, was Algorithmen, Performance und Co.
angeht.
Man muss sich das Ganze ja nur anschauen, wo das eigentlich ein Problem wird, und zwar, wenn du ganz viele Daten hast.
Das hast du halt klassischerweise in der Datenbankwelt oder klar, Google hat wahrscheinlich auch sehr viele Daten.
Wenn du eine kleine Hashmap hast mit 200 Einträgen, ist das komplett egal.
Aber wenn du natürlich Millionen von Einträgen hast, dann wird es schon ein Thema, muss ich meine Datenstruktur locken.
um irgendwas zu ändern oder zu resizen.
Und dann ist das natürlich ein ganz anderes Thema.
Darum haben die DatenbankentwicklerInnen natürlich viel mehr ein Augenmerk auf solche Dinge natürlich auch geworfen.
Und das ist ein klassisches Problem, wenn du ein Index-Update ist.
Eine Gefahr, die ich euch noch mitgeben möchte, weil die wird oft übersehen.
Wenn du eine Hash-Funktion hast, um deinen Index zu bauen, pass bitte auf, welche Hash-Funktion du nutzt und welchen Content du hashen möchtest.
Warum?
Es gibt Hash-Funktionen, die eine Komplexitätsalgorithmus von O von N oder vielleicht sogar höher haben.
Das bedeutet, dass die Länge des Contents, den du da hashen möchtest, teilweise auch auf die Dauer der Hash-Funktion schlagen kann.
Wenn du also einmal die Bibel durch eine Hash-Funktion jagst, dann wird das in der Regel länger dauern, als wenn du den Namen Wolfgang hashen möchtest.
Und wenn du jetzt nicht nur einmal die Bibel machst, sondern sehr oft die Bibel und wenn du nicht nur einen Request sendest, So viele Requests, wie es Kirchen auf dieser Welt gibt, dann kann das sein, dass nur durch die Hash-Funktion eine Denial-of-Service-Attacke ausgeführt wird, weil die Hash-Funktion so teuer ist, weil du einfach dauerhaft versuchst, einen sehr großen Content zu hashen.
Das ist ein gängiger Angriffsfaktor bei Login-Formularen.
Du knallst einfach ein unglaublich langes Passwort da rein, also wirklich so 500 Mal die Bibel und auf einmal merkst du, der Server braucht enorm lange zum Antworten.
Dann weißt du, du hast da was getroffen.
Das ist eine Timing-Attacke und das funktioniert natürlich überall, wo du eine suboptimale Hash-Funktion gewählt hast.
Deswegen ein bisschen aufpassen, was ihr da als Key versucht zu hashen und welche Funktion ihr habt.
Einen kleinen Baumausflug möchte ich noch machen und zwar den sogenannten TRIE, geschrieben T-R-I-E, also TRIE, aber aussprechen tut man es üblicherweise.
TRIE kommt von Retrieval.
Information Retrieval, Text Retrieval.
Und jetzt befinden wir uns schon in dem ganzen Bereich von Text-Suche, String-Suche, weil der klassische B-Baum, der wird ja üblicherweise mit Integers gefüllt.
Man kann natürlich Text auch genauso reinstecken.
Aber es gibt natürlich Bäume, die optimiert sind für Text.
Weil was ist das größte Problem mit Text, Andi?
Die sind scheiße zu vergleichen.
Ja, das auch.
Und was damit zusammenhängt, dass sie scheiße zu vergleichen sind, ist die Größe.
Integer-Werte im Hintergrund als eine Zahl.
Ist halt üblicherweise einfach lang.
Und das ist eigentlich immer das Problem, wenn man einen Index baut.
Weil ein Index ist ja immer in irgendeiner Form eine Kopie oder ein View auf die Daten.
Das heißt, man muss was duplizieren.
Wenn man jetzt Text dupliziert, ist das üblicherweise ein Problem, weil es einfach viel Speicherplatz braucht und dann auch dementsprechend langsam wird.
Der Try ist in gewisser Weise Vergleichbar mit einem B-Baum ist halt auch ein Baum.
Der Unterschied ist, du hast jetzt keine Zahl auf den Knoten, sondern du hast einen Buchstaben und du trennst.
Je nachdem ist es ein Buchstabe, der weiter vorne im Alphabet ist, weiter hinten im Alphabet und so werden deine Kinderknoten aufgeteilt.
Also das ist die recht naive Herangehensweise.
Ich mache einen klassischen Baum, verwende halt Buchstaben.
für meine Elemente.
Jetzt werden diese Bäume natürlich sehr, sehr groß und darum hat man da natürlich auch Optimierungen draufgelegt.
Patricia Try zum Beispiel ist so eine, wo man dann zum Beispiel Substrings, die gemeinsam in Wörtern vorkommen, dass man die in einen Knoten legt.
Also wenn du jetzt zum Beispiel Engineering Kiosk hast, Engine, Engage, Enlarge, whatever it is, dann hast du das ENG oder EN, hast du zum Beispiel als Entscheidungskriterium auf einem Knoten liegen und alles, was denselben Sub-String hat, wird da dann dementsprechend gemeinsam abgespeichert.
So sparst du dir natürlich Buchstaben, weil sonst müsstest du bei E springen, bei N springen, bei G springen, bei I springen und hättest immer neun Knoten.
Und so komprimierst du die Strings, die eben mehrfach vorkommen in verschiedenen Wörtern auf einen Knoten.
Das ist so eine Optimierung, heißt eben auch Radix Tree, Adaptive Radix Tree gibt es nochmal, der da dementsprechend nochmal mehr drauflegt und adaptiert.
Also man sieht schon, die Bäume sind eigentlich alle sehr, sehr ähnlich aufgebaut.
Es ist dann nur die Frage, was speichere ich in den Knoten ab?
Wie groß designe ich so ein Knoten?
Was sind meine Kriterien?
Um zu entscheiden, springe ich nach links, rechts, in der Mitte zu einem Kinderknoten?
Und das sind eigentlich die einzigen Unterscheidungsmerkmale.
Der klassische Baum.
mit logarithmischer Komplexität ist eigentlich immer vorhanden und ist eigentlich so Basis von fast jedem Index.
Das Beispiel, was du gerade genannt hast, passt eigentlich sehr gut für mein praktisches Beispiel, denn wo wird ein Try oder ein Red X-Stree eigentlich verwendet?
Und zwar findet der sich wirklich, wirklich oft in Routing-Libraries, also ich sage mal in HTTP-Router oder ähnliches von Web-Applikationen.
Denn die meisten Web-Frameworks haben irgendwo eine Definitionsstelle, wo du deine Routen definierst.
engineeringkiosk.dev slash podcasts, engineeringkiosk.dev slash podcast slash Episodentitel, engineeringkiosk.dev slash impressum, engineeringkiosk.dev slash host slash Wolfgang und so weiter und so fort.
Und ihr merkt schon, slash host slash Wolfgang, slash host slash Andy, das Wort Host ist doppelt, kann ein Knoten sein.
HTTP-Routen, besonders dynamische HTTP-Routen, wo du zum Beispiel dynamische Elemente hast, wie zum Beispiel einen Episodentitel, wie zum Beispiel irgendwelche Get-Parameter vielleicht sogar, die da damit einfließen können, können perfekt eigentlich in einem solchen Tree, in einem solchen Try, Entschuldigung.
Es ist ja auch ein Tree, ist ja okay.
Ein Try-Tree.
Ja, da ist es wieder Try.
Es ist schwierig, aber am Ende ist es immer ein Tree.
Du hast recht.
Das ist ein gutes Beispiel, was du nennst.
Jeder, der VS Code verwendet, kennt das auch.
Wenn man einen Ordner hat, wo nur ein anderer Ordner ist und keine anderen Ordner oder Dateien liegen, dann werden zwei Ordner zusammengefasst und auf eine Ebene gezogen.
Das heißt, du siehst dann nur Ordner slash Subordner und du kannst es gar nicht aufklappen.
Es wird zusammengezogen.
Das ist eigentlich die Vorgehensweise, was ein Reddix-Tree auch macht.
Logisch, würde ich fast sagen, wenn man auf solche Dinge blickt, aber wenn man das natürlich dann dementsprechend implementiert und optimiert implementiert, steckt schon da mehr dahinter.
Du kannst die ganze Sache natürlich auch in der Hashmap fahren, dann hast du aber wieder die Duplikation von den URL-Präfixen, dann hast du gegebenenfalls Probleme mit dynamischen Parametern und so weiter und so fort.
Deswegen bei sehr, sehr vielen HTTP-Routern wird das verwendet.
Und ich habe euch mal eine HTTP-Router-Library in Go verlinkt.
die sogar in der Readme da tiefer drauf eingeht, wie bzw.
warum dieser Try in der Implementierung verwendet wird.
Und was ganz klassisch immer im Vergleich zu einer Hash-Map oder zu einem Hash-Index ist, du kannst auch da wieder keine Range-Queries fahren, weil so bekommst du natürlich total easy, gib mir alle Unterseiten vom Engineering-Kiosk, das ist ein Knoten, der Engineering-Kiosk.dev-Knoten und alles, was darunter liegt, sind die Webseiten.
Eine superschnelle Anfrage, mach das mal mit einem Hash-Index, hast du gar keine Chance, da musst du durch, deinen kompletten Datenstamm durchgehen, weil der Hash-Index eben nur punktuell funktioniert, wenn du genau weißt, was du suchst.
Okay, Bäume, Bäume, Bäume.
Bäume sind super, gar keine Frage.
Aber mein Partner war Gärtner.
Und was machen Gärtner?
Gärtner züchten Blumen.
Und was hast du vorhin erwähnt?
Den Blumenfilter.
Wo ist der Zusammenhang da?
Ich sehe schon, du hast ein Problem mit Bäumen.
Du hast erst schon auf den Hash-Index übergeleitet, jetzt leitest du auf den Blumenfilter über.
Grundsätzlich gibt es natürlich auch ganz viele Indexstrukturen, die keine Bäume sind.
Der Bitmap-Index ist auch so einer.
Und der Bitmap-Index ist noch ein Index im Gegensatz zum Blumenfilter.
Darum heißt er ja auch nicht Blumenindex, sondern Blumenfilter.
Aber starten wir mal kurz beim Bitmap-Index.
Der Bitmap-Index ist eigentlich nichts anderes als eine große Bitmaske.
Kennt man ja, 0, 1, 0, 1, 0, 0, whatever.
Und am besten funktioniert der, wie der Name schon sagt, bei binären Feldern, zum Beispiel aktiv, nicht aktiv.
Und ich speichere jetzt einfach, anstatt diese ganze Tabelle in irgendeiner Form abzuspeichern oder ein B-Baum, speichere ich mir einfach eine lange Kette von Nullen und Einsen.
Null ist inaktiv, Eins ist aktiv.
Und dadurch Bits ja super schnell verarbeitbar sind, kann ich da auch relativ schnell durchgehen und sagen, find mir alle aktiven Zeilen, Einträge.
die ich gespeichert habe.
Also das ist ein Bitmap-Index, hat gar nichts mit Boyman zu tun, ist aber natürlich limitiert, weil im Idealfall ist es binär oder ich muss dann für jede Ausprägung einen eigenen Bitmap speichern.
Also wenn ich jetzt zum Beispiel einen Status von einem Ticketsystem habe, offen, open, closed, abgelehnt oder nicht nachvollziehbar, dann muss ich für alle, die offen sind, einen Bitmap-Index machen, für alle, die geschlossen sind, einen Bitmap machen und für alle Abgelehnten auch einen Bitmap.
Also da wird es dann schon komplizierter.
Eignet sich aber natürlich super, um diese ganzen Performance-Vorteile heutzutage von den CPUs auszunützen.
SIMD, Single Instruction Multiple Data.
Zusätzlich ist das natürlich sehr platzsparend.
Das heißt, es kann auch wieder schnell optimiert werden.
Es liegt alles hintereinander.
Das heißt, ich kann es so richtig schön einmal durch die CPU durchpipen.
Und was man auch oben draufknallen kann auf diese Bitmap-Index-Strukturen, ist eine Komprimierung, weil solche...
Bit-Abfolgen lassen sich auch super komprimieren.
Lauflängen-Codierung eignet sich zum Beispiel gut.
Also wenn ihr ganz viele Tickets habt, die aktiv sind, dann muss ich nicht alle Einzelnen von meinen aktiven Tickets speichern, sondern wenn die nächsten 100 IDs alle aktiv sind, dann speichere ich das nur einmal und sage, die nächsten 100 sind aktiv.
Das heißt, ich kann super komprimieren.
Gibt es auch noch komplexere Komprimierungsalgorithmen, Roaring, Bitmap.
Heißt es zum Beispiel dann, das ist dann noch hierarchisch organisiert.
Also da gibt es meistens Optimierungen obendrauf, die das halt nochmal verbessern und dementsprechend nochmal den Speicherplatz mehr ausnützen.
Und was den Speicherplatz richtig gut ausnützt, ist eben der sogenannte Bloomfilter.
Und wie gesagt habe, es ist ein Filter, kein Index.
Das heißt, ein Bloomfilter kann mir nicht sagen, wo liegt denn irgendwas.
Was aber ein Bloomfilter sagen kann, und das ist die Grundidee von einem Bloomfilter, habe ich einen gewissen Wert, eine Kundennummer, bei mir im Datensatz gespeichert oder nicht.
Und zwar kann er aber nur sagen, kommt dieser Datensatz nicht vor, das heißt, ich habe den garantiert nicht gespeichert oder vielleicht ist er gespeichert.
Das heißt, alles, was der Blumenfilter fix sagen kann, ist, ich habe etwas nicht gespeichert.
Und das ist eigentlich die Idee des Blumenfilters.
Dafür kann der super komprimiert das Ganze abspeichern und die kann da wirklich lange Zeichenketten unter Umständen in ein paar Bit oder Byte abspeichern und diese Fragen beantworten.
Und das ist eigentlich die große Stärke.
Also er ist einerseits super schnell, weil er super klein ist und ich kann da plötzlich Komprimierungen machen, die sonst eigentlich nicht möglich sind.
Weil wenn ich dich jetzt gefragt hätte, Andi, kann ich die Kundennummer irgendwie komprimieren?
Dann hätte ich es wahrscheinlich gesagt, nein, Integer, wie soll ich ein Integer komprimieren?
Das ist das Kleinste, was ich haben kann.
Ein Blumenfilter kann sogar Integer komprimieren.
Ich verliere natürlich Informationen, weil er nur mehr antworten kann, nein, diesen Kunden habe ich nicht.
Aber dafür habe ich eine Komprimierungsmethode, die sonst eigentlich klassisch nicht möglich war in dieser Form.
Wie funktioniert jetzt das Ganze?
Es werden mehrere Hashing-Funktionen verwendet, wie beim Hash-Index, aber multiple Hash-Funktionen.
Und das Ergebnis wird dann auf ein Bit, zum Beispiel in meinem Index gelegt.
Wenn ich zum Beispiel Andi jetzt in meinem Blumenfilter ablegen will und ich habe einen Blumenfilter mit 20 Bit, dann habe ich wahrscheinlich 20 Hash-Funktionen und die 20 Hash-Funktionen werden auf Andi aufgerufen und entscheiden jeweils, ist es 0 oder 1.
Und dann bekomme ich ein ganz individuelles Pattern heraus für Andi, wo ich einsetzen muss, meinen Blumenfilter und wo eben nicht eins gesetzt wird.
Und wenn ich jetzt später die Frage stelle, ist der Andi meinem Datensatz verfügbar, dann kann ich schauen, sind diese Einser von Andi alle eins gesetzt.
Wenn das der Fall ist, dann ist die Chance zumindest gegeben, dass Andi verfügbar ist.
Wenn da aber irgendwo Null steht, dann kann ich mit hundertprozentiger Sicherheit sagen, der Andi ist nicht in meinem Datensatz.
Weil wenn ich den Andi mal gesehen hätte in meinem Datensatz, dann hätte ich ja diese Bits an den jeweiligen Stellen auf eins gesetzt.
Perfekte Überleitung mit den Bits, muss ich dir wirklich sagen, denn mein Praxisbeispiel passt nämlich perfekt.
Und zwar folgendermaßen.
Praxisbeispiel wie immer, wo wird der Bloomfilter denn verwendet?
Ja, es wäre schlecht, wenn dein Beispiel nicht auf meine Erklärung passen würde, wie der Bloomfilter funktioniert.
Ich hoffe, dass er gleich funktioniert bei dir.
Jetzt nur mal so als SideTrack, auch ein Bloomfilter, die Datenstruktur ist im Redis auch verfügbar, wer das mal implementieren, wer damit mal rumstellen möchte.
Aber das lasse ich jetzt nur mal so als SideFact hier.
Denn es geht um Git.
Git implementiert einen Bloomfilter.
Wenn du den Command git log ausführst, und dort ein Argument übergibst, dann übergibst du in der Regel den Schar eines einzelnen Git-Commits, oder?
Ja.
Das wird mit hoher Wahrscheinlichkeit unten runter ein Hashmap-Lookout sein.
Weil der Schar von einem Git-Commit kannst du ja so, ich sag mal so als Primary Key von deinen Commits ansehen.
Richtig?
Ja, als Primary Key, wie man dann indiziert, ist nochmal eine andere Sache.
Genau, aber jetzt mal so ganz simpel.
Jetzt ist es aber so, du kannst auch eine Dateipfad an Git-Log geben.
Du kannst sagen git log minus minus und dann fahrt zu einer Datei.
Diese Operation ist relativ teuer, denn was Git unten drunter machen muss, der muss für jeden Git-Commit prüfen, ob sich die Datei, die du angegeben hast, gegenüber dem Parent in dem Baum, in dem Git-Baum geändert hat.
Das heißt eigentlich, unten drunter müssen verschiedene Bäume kontinuierlich für jeden Git-Commit gedifft werden.
Gibt es da eine Änderung und so weiter.
Tada!
Du merkst schon, wo wir hingehen.
Wir bauen eine Indexstruktur.
Und zwar nehmen wir da einen Bloomfilter.
Denn immer wenn ein Commit gemacht wird, wird der Commit Graph pro Commit in einen Bloomfilter überführt, wo dann verschiedene Bits gesetzt werden für diesen einzelnen Commit.
Und wenn du git log minus minus Pfad zu einer Datei machst, dann schaut der erst in den Bloomfilter nach.
Oh, habe ich hier was?
Und da hat er dann verschiedene Bits gesetzt und anhand der Bits, die gesetzt wurden, entscheidet er ja.
Diese Datei wurde geändert.
Nein, diese Datei wurde nicht geändert.
Oder maybe, wenn alle Bits gesetzt sind und nur in dem Fall von maybe, das ist ja dann probabilistisches Ergebnis, dann macht er die teure Operation von den Bäume-Diffen, die er sowieso gemacht hätte ohne die Indexstruktur.
Und das ist so ein schönes Beispiel, dass man eigentlich diese Indexstrukturen, ja würde ich sagen, zumindest wöchentlich verwendet.
Also ich muss mich korrigieren.
Wie gesagt, Indexstruktur kann man jetzt darüber streiten.
Ich würde es nicht Indexstruktur nennen, weil eine Indexstruktur kann die normal etwas zurückliefern oder sagen, wo der eigentliche Wert liegt.
Das kann ein Blumenfilter nicht.
Und ich bin ja der akademische Part in dem Podcast, darum probiere ich das jetzt wieder auf ein allgemeines Level zu heben, wo ein Blumenfilter sinnvoll ist.
Und zwar macht ein Blumenfilter natürlich nur da Sinn, wo ich viele Anfragen bekomme.
Und die Chance aber gering ist, dass eigentlich ein Wert in meiner Datenbank oder in meinem Datenset überhaupt verfügbar ist.
Weil sonst, wenn ich ständig die Info bekomme, ja, ist eh verfügbar, dann muss ich durch das ganze Datenset durch, ist natürlich schlecht.
Also es macht natürlich am ehesten Sinn, wenn die Antwort oft, nö, ist nicht bei mir im Datensatz ist.
Oder wenn das Anschauen an sich extrem teuer ist.
Das heißt, wenn ich jetzt zum Beispiel in einem Distributed System bin, Und ich will wissen, wo liegt denn der Wert auf Node 1, auf Node 2, auf Node 3?
Und ich müsste damit Netzwerk erstmal nachfragen.
Dann wäre das natürlich super langsam und ein Blumenfilter kann mir das natürlich im Vorhinein beantworten.
Und um noch ein Beispiel zu nennen, was Andis Lieblingsthema ist, Tiered Storage.
Das heißt, ihr habt verschiedene Storage Layer, irgendwie Storage Layer, die ganz schnell sind, meine Festplatte, irgendwelche Remote Storage Layer, die super langsam sind, die cold sind.
Da kann ich natürlich ein Blumenfilter davor setzen, damit die nicht, in mein Bergwerk gehen muss und auf irgendeinem Band nachschauen muss, ist da irgendwie ein Datum, eine Datei vorhanden, sondern das kann der Bloomfilter beantworten.
Der ist super kompakt und im Falle muss ich dann natürlich im Detail nochmal nachschauen.
Und aus dem Grund wird er übrigens auch bei LSM-Trees, das ist die Indexstruktur von RocksDB unter anderem, die Facebook hier auch verwendet, stark eingesetzt, weil das eben auch so ein Tiered Storage Modell verwendet.
Und jetzt habe ich einfach mal ein perfektes Beispiel, wo ihr mal einfach hart ganz dumpf Vibe-Coden könnt, auch wenn ihr jetzt sagt, oh, da rollen sich die Fingernägel hoch, aber der Wolfgang ist für die Theorie zuständig und ich bin der praktische Typ, deswegen pushe ich euch mal in die Richtung, springt doch einfach mal in eure KI, sagt, bau mir doch mal eine Blumenfilter-Implementierung, interviewe mich dazu zu meinen Datensätzen und dann forciere doch einfach mal eine Blumenfilter-Implementierung von Daten, die du kennst und dann lässt du dir das in deiner Sprache, deiner Wahl in einem Minimal-Code-Beispiel mal generieren und liest dir das durch, um einfach mal ein Verständnis zu kriegen.
Denn zumindest für mich hören sich diese theoretischen Konstrukte immer super an und ja, ich klicke dann die Slides immer durch und dann sehe ich dann die Trade-Offs und die Pro und die Cons und dies und das, alles gut.
Aber richtig Klick macht es halt, wenn die ganze Sache auf Daten läuft, die ich kenne, also wo ich Domänen-Experte vielleicht bin.
Und wenn ich mir per KI einfach drei, vier Projekte generieren lasse.
Unabhängig davon, ob die Struktur, auch wenn ich bezeichne Blumenfilter jetzt auch als Indexstruktur, kann der Wolfgang, das Geile ist ja, wir leben ja remote auf.
Der Wolfgang kann mich gar nicht hauen.
Ist viel zu weit weg.
Aber dann habe ich auf jeden Fall ein deutlich höheres Verständnis, wo ich dann den Kram hoffentlich besser verstehe.
Und Blumenfilter ist ja wirklich so der neue heiße Scheiß, zumindest seit, ja, ich würde mal sagen, 15 Jahren.
Aber wenn man zurückblickt, erfunden ist das Ganze 1970 worden.
Also lang, lang, bevor das eigentlich alles ein Thema war.
Da sieht man, wie lang sowas dann wirklich benötigt, bis es dann schlussendlich auch die Anwendung findet.
Und Andi, du kannst es gerne Indexstruktur nennen.
Ist vollkommen okay.
Es ist ja eine Datenstruktur.
Also soweit können wir uns ja drauf einigen.
Und vielleicht noch als kleine Side-Note.
Ich habe ziemlich lang gebraucht, bis ich Blumenfilter richtig verstanden habe.
Also ich habe da einige Infos durchgelesen damals.
Und bis ich es so richtig verstanden habe, hatte es eine Zeit.
wirklich benötigt.
Insofern finde ich deinen Approach super gut, weil früher war das natürlich nicht so einfach, da irgendwie ein Beispiel zu sehen oder welche Bits werden denn da belegt, wenn ihr da irgendein Wort eingibt.
Da hat es ja keine Online-Simulatoren gegeben, die dir das so einfach berechnet haben.
Jetzt kannst du dir das einfach wipecoden oder wirklich mal ein persönliches Beispiel ausgeben lassen und du kannst gezielt Fragen stellen.
Also es ist eigentlich ideal, um irgendwas zu lernen.
Ich mache das gar nicht so oft, dass ich gezielt Fragen stelle.
Ich sage dem oft initial, okay, kommentiere das.
Für einen Junior Engineer oder ähnliches.
Oder für einen Five-Year-Old.
Natürlich ist das dann super exzessiv und da steht dann super viele Kommentare.
Alles gut.
Aber ich habe es ja dann ganz kurz generiert.
Drei, vier Minuten.
Lese es mir durch und danach schmeiße ich es ja eh wieder weg.
Ich will es ja nur verstehen.
Von daher, da muss ich schon zugeben, jetzt mal unabhängig davon, ob das in Produktion geschippt wird oder nicht, das nenne ich mal reale Code Generation.
Aber wer immer noch dran ist, nicht weggepennt ist und noch mehr von so einem Kram hören möchte, Hört sich die Episode 151 an, weil da haben wir über ganz viele Bäume gesprochen, andere Bäume, und zwar über Geoindizes, also räumliche Datenstrukturen und Indexstrukturen.
Und wer weniger auf Bäume steht, der hört sich Andis fast Lieblingsfolge, würde ich sagen, an.
Und zwar die 146, wo der Andi über Doom, über das Computerspiel, philosophiert und...
Viel technologische Trivia auch erzählt, aber unter anderem auch, was hinter diesen ganzen räumlichen Indexstrukturen steht, damit man das Rendering verbessert und die Lichtstrahlen irgendwie richtig berechnen kann und so weiter.
Also auch das sind Indexstrukturen.
Die Doom-Folge ist definitiv auch zu empfehlen.
146.
Wie ihr es von uns gewohnt seid, alle Links in den Shownotes.
Und jetzt erwarte ich eigentlich von jedem als Hausaufgabe.
dass ihr mal in die Codebase springt, an der ihr professionell arbeitet, schmeißt die KI drauf und sagt, welche Indexstrukturen habe ich denn hier im Quellcode verwendet?
Und lasst euch mal da die Codezeilen zeigen.
Und wenn ihr dann in die Discord-Community kommt und die Anzahl der verschiedenen Indexstrukturen einfach mal postet, der Gewinner mit der Codebase, mit den meisten verschiedenen Indexstrukturen, kriegt einen Kaffee von uns.
Wie wir den übermitteln, weiß ich jetzt auch noch nicht.
Kriegen wir schon irgendwie hin auf irgendeiner Konferenz.
Da bin ich mal gespannt.
Am geilsten wäre mit so ein bisschen Kontext, wie viele Lines of Code hat denn die Codebase, was macht die Codebase denn und so weiter und so fort.
Da bin ich mal gespannt.
Zählen da dann die Datenbank-Index-Strukturen schon mit, oder?
Weil die sieht man ja in der Codebase nicht.
Nee, nee, nee, schon die im Quellcode.
Ah, die im Code, okay.
Ja, ja, ganz genau.
Und wenn du jetzt zweimal einen Bloom-Filter hast, zählt das eins, ja?
Weil ich sage ja verschiedene.
Dann gewinnen alle, die Node.js verwenden, oder?
Weil da hat man garantiert so viele Packages eingebunden und die alle wieder irgendwelche anderen Index-Strukturen verwenden.
Oder muss das auf der ersten Ebene sein?
Ich sehe schon, Andi haut da immer so diese Gewinnspiele raus und ich muss mich dann um diese rechtlichen Themen kümmern.
Oder wir machen es einfach so, wir entscheiden das am Ende, wer gewinnt.
Ja, irgendwo müssen wir die Power ja auch mal ausnutzen.
Eben, genau, so machen wir das.
Wer ihm das nicht gefällt, der wird einfach wieder raus, der ist gut, der wird rausgeschmissen, relativ einfach.
Das ist bisher noch nie passiert, aber schauen wir mal.
Irgendwann ist immer das erste Mal.
So, das war's von uns.
Ich hoffe, ihr habt eine Sache mitgenommen.
Wie immer hören wir uns nächste Woche.
Und falls ihr noch nicht alte Episoden gehört habt, dann wählt einfach mal irgendeine andere Episode aus, hört euch die an und empfiehlt die einfach mal einer Kollegin und einem Kollegen weiter.
Das war's von uns.
Wir sind weg und tschüss.
Ciao.