#273 Bäume, Hashes, Bitmaps: Performance ist kein Zufall

Warum werden Systeme langsam, obwohl die Hardware doch immer
schneller wird? Und warum endet die vermeintlich einfache Lösung
so oft in einem Stack-Wechsel, der neue Probleme schafft statt
alte zu lösen? Genau da setzen wir in dieser Episode an. Wir
schauen auf Indexstrukturen, Datenstrukturen und die oft
übersehene Frage, wie Workload, Hardware, Lese- und
Schreibzugriffe und Algorithmen zusammenhängen. Denn häufig ist
nicht die Datenbank schuld, sondern die falsche Struktur für den
falschen Job.


In dieser Episode sprechen wir über Red Black Trees, B-Bäume,
B-Plus-Bäume, Hash-Indizes, Trie, Radix Tree, Bitmap Index und
Bloomfilter. Wir machen das nicht abstrakt, sondern mit konkreten
Beispielen aus der Praxis. Etwa mit Nginx und Timeout-Management
im Event-Loop, mit HTTP-Routern und Prefix-Suche, mit Git und
Bloom Filtern für schnellere Dateipfad-Abfragen oder mit
Alerting-Systemen und Hashmaps. Dabei geht es auch um Big O,
Cache Lines, Range Queries, Rehashing, Performance-Basics und die
Frage, wann Optimierung sinnvoll ist und wann sie nur
Overengineering produziert.


Wenn du besser verstehen willst, warum manche Software unter Last
einknickt und wie du mit dem richtigen Datenmodell, sauberen
Metriken und etwas Architekturverständnis deutlich weiter kommst,
ist diese Folge für dich. Und vielleicht ist die wichtigste
Erkenntnis am Ende gar nicht, welche Indexstruktur die beste ist,
sondern dass du sie in deiner eigenen Codebase vermutlich längst
benutzt, oft nur ohne es zu merken.


Bonus: Blumenfilter sind keine Blumen und streng genommen nicht
mal ein richtiger Index.





Unsere aktuellen Werbepartner findest du auf
https://engineeringkiosk.dev/partners





Das schnelle Feedback zur Episode:


(top)  (geht
so)



Anregungen, Gedanken, Themen und Wünsche

Dein Feedback zählt! Erreiche uns über einen der folgenden Kanäle
…


EngKiosk Community:
https://engineeringkiosk.dev/join-discord 

LinkedIn: https://www.linkedin.com/company/engineering-kiosk/

Email: stehtisch@engineeringkiosk.dev

Mastodon: https://podcasts.social/@engkiosk

Bluesky:
https://bsky.app/profile/engineeringkiosk.bsky.social

Instagram: https://www.instagram.com/engineeringkiosk/




Unterstütze den Engineering Kiosk

Wenn du uns etwas Gutes tun möchtest … Kaffee schmeckt uns
immer 


Buy us a coffee: https://engineeringkiosk.dev/kaffee




Links

Engineering Kiosk Episode #146 Warum ist Doom so faszinierend
für die Software-Entwicklung?:
https://engineeringkiosk.dev/podcast/episode/146-warum-ist-doom-so-faszinierend-f%C3%BCr-die-software-entwicklung/

Engineering Kiosk Episode #28 O(1), O(log n), O(n^2) - Ist
die Komplexität von Algorithmen im Entwickler-Alltag relevant?:
https://engineeringkiosk.dev/podcast/episode/28-o1-olog-n-on2-ist-die-komplexit%C3%A4t-von-algorithmen-im-entwickler-alltag-relevant/

Engineering Kiosk Episode #269 Performance-Basics:
Indexstrukturen, Cache-Lokalität & Zugriffsmuster:
https://engineeringkiosk.dev/podcast/episode/269-performance-basics-indexstrukturen-cache-lokalit%C3%A4t-zugriffsmuster/

Engineering Kiosk Episode #73 Cache-freundliches
Programmieren, CPU-Caches, Ersetzungsstrategien und
Cache-Invalidierung:
https://engineeringkiosk.dev/podcast/episode/73-cache-freundliches-programmieren-cpu-caches-ersetzungsstrategien-und-cache-invalidierung/

Engineering Kiosk Episode #265 One Billion Row Challenge:
Java mit mmap, Unsafe & richtig vielen Bit-Tricks:
https://engineeringkiosk.dev/podcast/episode/265-one-billion-row-challenge-java-mit-mmap-unsafe-richtig-vielen-bit-tricks/

julienschmidt/httprouter - A high performance HTTP request
router that scales well:
https://github.com/julienschmidt/httprouter

Engineering Kiosk Episode #151 Räumliche Indexstrukturen:
Grundpfeiler in Geo-Systemen, Games und Machine Learning:
https://engineeringkiosk.dev/podcast/episode/151-r%C3%A4umliche-indexstrukturen-grundpfeiler-in-geo-systemen-games-und-machine-learning/

Alertmanager: https://github.com/prometheus/alertmanager

NGinx Source Code: https://github.com/nginx/nginx

Redis Bloom Filter:
https://redis.io/docs/latest/develop/data-types/probabilistic/bloom-filter/




Sprungmarken

(00:00:00) Indexstrukturen und Skalierung: Warum Datenstrukturen
entscheidend sind


(00:04:17) Info/Werbung


(00:05:17) Indexstrukturen und Skalierung: Warum Datenstrukturen
entscheidend sind


(00:07:13) Workload, Hardware und Big O: Wie du Performance
richtig einordnest


(00:12:47) Bäume als Indexstrukturen: RAM, Festplatte und moderne
Hardware


(00:21:26) Red Black Trees in der Praxis: Sortierung, Balance und
Nginx-Timeouts


(00:24:34) B-Bäume und B+ Bäume in Datenbanken und Hauptspeicher


(00:28:39) Hashindex und Hashmap: Punktabfragen, Kollisionen und
Rehashing


(00:34:09) Redis, Incremental Rehashing und Hashing-Fallen in der
Praxis


(00:39:51) Trie und Radix Tree: Textsuche, Routing und
URL-Präfixe


(00:45:29) Bitmap Index und Bloomfilter: Kompakte Strukturen für
schnelle Filter


(00:50:44) Bloomfilter in Git, verteilten Systemen und Tiered
Storage


(00:54:51) Challenge für die eigene Codebase, gewinne einen
Kaffee



Hosts

Wolfgang Gassler (https://gassler.dev) 

Andy Grunwald (https://andygrunwald.com/)




Community

Diskutiere mit uns und vielen anderen Tech-Spezialist⋅innen in
unserer Engineering Kiosk Community unter
https://engineeringkiosk.dev/join-discord