#164 Suchalgorithmen: Lineare- und Binäre Suche & Indizes mit Stefan Macke vom IT Berufe Podcast

Suchalgorithmen: Lineare- und Binäre Suche mit Stefan Macke vom IT Berufe Podcast.

Im Engineering Kiosk Adventskalender 2024 sprechen befreundete Podcaster⋅innen und wir selbst, Andy und Wolfi, jeden Tag kurz & knackig innerhalb von wenigen Minuten über ein interessantes Tech-Thema.

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

Das schnelle Feedback zur Episode:

👍 (top) 👎 (geht so)

Sprungmarken

(00:00:00) Suchalgorithmen: Lineare- und Binäre Suche

Hosts

Wolfgang Gassler (https://mastodon.social/@woolf)
Andy Grunwald (https://andygrunwald.com/)

Feedback

EngKiosk Community: https://engineeringkiosk.dev/join-discord
Buy us a coffee: https://engineeringkiosk.dev/kaffee
Email: stehtisch@engineeringkiosk.dev
LinkedIn: https://www.linkedin.com/company/engineering-kiosk/
Mastodon: https://podcasts.social/@engkiosk
Bluesky: https://bsky.app/profile/engineeringkiosk.bsky.social
Twitter: https://twitter.com/EngKiosk

Transkript

Das Transkript wurde automatisiert per Speech-to-Text erstellt und kann daher Fehler enthalten.

Andy Grunwald (00:00:04 - 00:00:33)

Ein neuer Tag im Dezember, ein neues Engineering Kiosk Adventskalendertürchen für euch. Wir starten die Episode wieder mit einem Witz, beziehungsweise auch einfach nur der Wahrheit. Was ein Schenkelklopfer. Aber nun gut. Diese Episode beinhaltet einen Community Beitrag aus der deutschsprachigen Softwareentwicklungspodcast Community zweitausendein. Ich übergebe das Mikrofon an Stefan. Los geht's.

Stefan Macke (00:00:33 - 00:14:17)

Moin aus dem nicht ganz so hohen Norden, aus Vechta, zwischen Bremen und Osnabrück in Niedersachsen. Mein Name ist Stefan Macke und ich war in der zwei und neunzigste Episode hier zu Gast bei Andi und Wolfgang zum Thema IT Ausbildung. Ich bin nämlich auch der Host des IT Berufe Podcasts. Falls du selber noch in der Ausbildung bist oder Ausbilder oder Ausbilderin, hör da gerne mal rein. Heute habe ich mal ein Thema mitgebracht für den Adventskalender, das relevant ist für meine Azubis und für auch alle anderen Azubis im IT Bereich. Und zwar Datenbankindizes oder einen Datenbankindex in der Einzahl. Und das möchte ich gerne verbinden mit zwei anderen interessanten Themen, und zwar der Komplexität von Algorithmen und zwei verschiedenen Suchalgorithmen, nämlich der linearen Suche und der binären Suche. Was das alles miteinander zu tun hat, das würde ich jetzt mal im folgenden erzählen. Es soll jetzt hier nicht hochtechnisch wissenschaftlich werden, das heißt, ich gehe jetzt nicht in die konkreten super feinen Details rein, sondern eher auf einem abstrakten Niveau, weil ich glaube, das Thema ist erstmal für alle interessant. Wer sich dann wirklich im Detail noch eingraben will, findet da bestimmt ganz viele wissenschaftliche Paper und ich weiß nicht was, aber für die IHK Prüfung reicht es auf jeden Fall so oberflächlich, wie ich es heute erzähle. Wir steigen mal rein, würde ich sagen. Also ein Datenbankindex, wer das noch nie gehört hat, wenn ich in einer relationalen Datenbank nach z.B. einer Spalte suchen möchte, Beispiel, ich habe eine Tabelle Personen und da gibt es Vorname, Nachname, Anschrift und so weiter und ich möchte nach dem Nachnamen suchen, dann wäre es ganz sinnvoll, wenn ich auf die Spalte Nachname einen sogenannten Index lege. Und Index, das ist quasi gleichbedeutend mit dem, was wir aus der Offline Welt, also der nicht IT Welt kennen, nämlich dem Index in einem Buch. Wir haben uns in der IT ganz, ganz viele Begriffe aus dem wahren Leben geborgt, wie z.B. den Desktop, auf dem wir jeden Tag arbeiten, ist nichts anderes als unsere Schreibtisch Oberfläche. Und Ein Index in einem Buch macht genau das gleiche, was wir jetzt hier brauchen. Und zwar kann ich in dem Index, sortiert ist dieser Index, suchen nach einem Stichwort z.B. nach, weiß ich nicht, Datenbank und dann steht in dem Index Datenbank auf Seite sieben, 59 und 373 findest du was zum Thema Datenbanken. Und dann kann ich mit dieser Seitenzahl im Buch das Thema schneller finden, als wenn ich einfach von vorn bis hinten das Buch durchlesen muss, um dann zu gucken, wo irgendwas zu Datenbanken steht. Das ist die Idee eines Index, und den haben wir eins zu eins auf Datenbanken übertragen. Beispiel meine nachname Spalte in der Personentabelle. Wenn wir uns vorstellen, da sind ganz, ganz viele Personen drin und die sind einfach random irgendwie dort gespeichert, z.B. Ÿousand anhand der Reihenfolge, wo sie tatsächlich gespeichert wurden, dann kann natürlich der Nachname, den ich suche, irgendwo in dieser Tabelle stehen und ich weiß es nicht. Und wie ich den dann finde, ist, ich gehe von vorn bis hinten jeden einzelnen Datensatz durch und gucke, ob der vielleicht den Nachnamen hat, den ich suche. Und das dauert natürlich ziemlich lange. Sehen wir uns auch gleich im Detail angucken, wie lange das dauert und wie man das schneller macht. Das ist erstmal das Problem und das kann ich bei einem Index lösen. Ich lege einen Index auf die Spalte Nachname und was dort im Prinzip passiert, und hier bitte jetzt nicht zu viel technische Details erwarten, ganz grob erklärt ist es quasi eine weitere Tabelle. Und zwar ist diese Tabelle nach dem Nachnamen sortiert und hat dann eine zusätzliche Spalte, und zwar mit dem Schlüssel der Datensätze, wo der Nachname mit diesem speziellen Wert drinsteht. Hört sich alles ganz kompliziert an, ist aber ganz einfach. Wir machen mal unsere Personentabelle. Mein Name ist Stefan Macke. Irgendwo steht also der Datensatz mit Nachnamen Macke. Und wenn ich jetzt einen Index auf den Nachnamen lege, dann wird dieser Name Macke, der da drin steht, quasi in diese neue Tabelle als Schlüssel eingetragen. Macke steht vorne und hinten in der zweiten Spalte. Hinter diesem Ÿousand Nachnamen steht dann die Schlüssel der Datensätze, die den Nachnamen Mackey haben. Und wenn ich jetzt in meiner ursprünglichen Tabelle nach Macke suche, dann muss ich nicht jeden einzelnen Datensatz durchsuchen, sondern ich schaue in den Index, gehe direkt zum Eintrag Macke, finde den Datensatz 97 und kann jetzt mit dieser 97, mit diesem Schlüssel in der Originaltabelle, meine sieben und neunzigste Person öffnen und habe direkt meine gewünschte Person gefunden und muss nicht alle Datensätze durchgucken. Das ist erstmal die Idee eines Index. Und jetzt gucken wir uns mal an, was es mit dieser linearen und binären Suche auf sich hat. Denn so ein Index, der ist echt extrem schnell im Vergleich zu einer normalen Suche. Wie ich es gerade beschrieben habe, haben nämlich schon den ersten Such Algorithmus quasi gerade mitgelernt, nämlich die lineare Suche. Linear kennst du vielleicht noch aus der Mathematik, so wie eine Gerade, die irgendwie ansteigt oder fällt, ist eigentlich egal. Auf jeden Fall geht es immer geradeaus. Es gibt da keine Kurve, die mal hoch und runter geht, exponential etc. Sondern es geht einfach linear gerade hoch oder runter. Und genauso ist es, wenn ich in einer Tabelle linear suche, wenn ich von vorn bis hinten alle Datensätze mir angucken muss, weil ich kein Indiz habe, wo ich schneller die Sachen finde, dann ist es eine sogenannte lineare Suche. Und das heißt, je länger die Tabelle wird, desto länger dauert auch dieser Such Algorithmus, weil er sich ja immer mehr Datensätze anschauen muss. Und wie ist jetzt die sogenannte Komplexität? Das kennst du vielleicht auch. Man kann Algorithmen einteilen anhand ihrer Komplexität, das bedeutet, oder ihres Laufzeitverhaltens. Das bedeutet im Prinzip, wenn die Menge der Eingangsdaten zunimmt, um wie viel die Länge der Laufzeit sich erhöht. Und bei der linearen Suche ist es so, wenn ich die Eingangsmenge verdoppel, dann verdoppelt sich auch die Laufzeit des Algorithmus. Kann man sich auch vorstellen, ich hatte 100 Datensätze in der Tabelle, muss mir 100 Datensätze angucken. Wenn ich was suche, habe ich 200 Sätze in der Datenbank muss ich 200 Sätze mir angucken, also doppelte Laufzeit, weil doppelt so viele Datensätze drin sind. Und das ist erstmal gar nicht so schlimm schlecht, ehrlich gesagt, für so einen Algorithmus. Aber sobald ich ganz, ganz, ganz, ganz viele Datensätze in meiner Tabelle habe, dann wird es ein Problem. Und ich nehme jetzt einfach mal ein sehr großes Beispiel. Wir haben eine Tabelle mit 4 Milliarden Personen drin, dann muss ich 4 Milliarden Vergleichsoperationen machen, um z.B. eine Person mit dem Nachnamen Macke zu finden, weil ich muss mir ja jeden Datensatz einzeln angucken. Und 4 Milliarden, es könnte ein bisschen dauern, das muss also irgendwie schneller gehen. Und jetzt kommen wir nochmal auf den Index zurück, wie der jetzt nämlich funktioniert. Der setzt als allererstes mal voraus, dass die Liste, durch die ich da suchen will, sortiert ist. Denn wenn sie das ist, kann ich einen anderen Sortieralgorithmus, nicht Sortieralgorithmus, sondern Such Algorithmus darauf anwenden, und zwar die binäre Suche. Stellen wir uns vor, die Tabelle, wo unsere Nachnamen drinsteht, ist nicht sortiert. Dann kann die Datenbank den Nachnamen nur finden, indem sie jeden einzelnen Datensatz sich anschaut, weil es keinen Anhaltspunkt gibt, ob ich z.B. noch vor dem gesuchten Namen bin. Ob ich da drüber bin oder wie auch immer, weil die können ja irgendwie in dieser Liste stehen. Ist die Liste aber sortiert, habe ich, wenn ich mir einen Datensatz anschaue, einen Anhaltspunkt, in welche Richtung ich weitersuchen muss. Wenn ich z.B. nach einer Macke suche und bin aber gerade bei einem Datensatz, der irgendwie Meier heißt und Meier mit E, um es jetzt mal etwas einfacher zu machen, dann weiß ich, ich bin schon zu weit, weil Marke steht natürlich vor Me Maier. Das heißt, ich muss in die Richtung nach hinten weitersuchen, um den Datensatz zu finden. Und das ist so die Idee der binären Suche. Wenn ich eine sortierte Liste habe, dann kann ich jetzt ganz einfach, wenn ich gar keine Ahnung habe, wo ich anfangen soll, einfach in der Mitte der Liste anfangen. Ich gehe einfach auf den mittleren Datensatz und guck, wo bin ich denn? Bin ich schon an Macke vorbei oder kam Macke noch nicht? Und wenn ich das rausgefunden habe, dann weiß ich, dass ich in der jeweiligen Hälfte der Liste weitersuchen muss. Bin ich z.B. beim Buchstaben d gelandet in der Mitte, dann weiß ich, dass m kommt nach dem d. Also muss ich in der zweiten Hälfte der Tabelle, die ich jetzt gerade durch die Auswahl meines mittleren Elements geteilt habe, weitersuchen. Und dann mache ich das genauso. Dann nehme ich den zweiten Teil der Tabelle und teile das wieder in der Mitte und gehe von dort auf das mittlere Element und gucke, wo bin ich? Bin ich schon an Macke vorbei oder nicht? Und wenn ich weiß, in welche Richtung ich weitersuchen muss, dann kann ich das immer weiter teilen. Das heißt, die Liste wird bei jedem Suchvorgang halbiert. Erstmal in der Mitte der ganzen Liste, dann in der Mitte der jeweiligen Hälfte, dann in der Mitte des jeweiligen Viertels und so weiter. Das heißt, mit jedem Suchvorgang halbiere ich die Anzahl der Elemente, die ich mir noch angucken muss, weil ich die ausschließen kann, weil ich weiß, dass ich entweder schon drüber bin oder noch drunter bin. Und das hört sich jetzt erst mal gar nicht so spannend an, aber das ist ein extremer Vorteil, was die Anzahl der Suchvorgänge angeht. Mein Beispiel von eben mit den 4 Milliarden Datensä lineare Suche, 4 Milliarden Vergleiche. Jetzt ist die Frage, wie viele Vergleiche bräuchten wir denn bei einer binären Suche? Das heißt, bei jedem Suchvorgang halbieren wie die Liste. Das könnten wir jetzt ausrechnen. 4 Milliarden geteilt durch zwei, 2 Milliarden geteilt durch zwei sind 1 Milliarde geteilt durch zwei. Das machen wir so lange weiter, bis wir bei eins angekommen sind, denn dann haben wir unser Element gefunden. Und jetzt kann man, wenn man ein bisschen die Zweierpotenzen aus der IT so kennt, relativ schnell sagen, das könnten ungefähr zwei und dreiig Suchvorgänge sein. Denn wenn du weißt, zwei hoch zwei und dreiig sind vier, irgendwas Milliarden, das ist übrigens auch die Länge eines Integers, z.B. in in Java, da passen 4 Milliarden verschiedene Werte rein. Das heißt, wenn ich 4 Milliarden Datensätze in meiner Tabelle habe und jedes mal bei jedem Suchvorgang die Liste halbiere, dann brauche ich nur zwei und dreiig Halbierungsvorgänge und bin beim gesuchten Wert. Wenn wir das mal vergleichen, die zwei und dreiig im Vergleich zu 4 Milliarden, das ist extrem viel schneller. Das ist ja quasi 100 Millionen mal schneller als die lineare Suche. Und deswegen ist es so so wichtig, dass wir in unseren Datenbanken Indizes für Spalten setzen, die wir häufiger durchsuchen wollen, weil die Datenbank sonst echt viel zu tun hat. Und das macht sich wirklich krass bemerkbar. Schon bei Tabellen, die nicht so viele Datensätze, wie jetzt ich beschrieben habe, enthalten haben, enthalten, wird die Laufzeit extrem viel schneller, wenn ich einen Index auf den Suchspalten habe. Von daher wichtiges Tool, haben jetzt auch gelernt warum? Weil ich in einem Index einer sortierten Liste binär suchen kann und das viel, viel, viel schneller ist als die lineare Suche. Jetzt können wir noch mal kurz klären, wie viel schneller genau. Wenn wir überlegen, bei jedem Suchvorgang wird der Wert halbiert, dann ist das die komplett Komplexität O von Logarithmus n. Die Komplexität einer linearen Suche ist O von n. N ist die Anzahl der Listenelemente. Wenn ich n verdoppelt, wird auch der Algorithmus doppelt so lang. Wenn ich log n habe, also Logarithmus von n, dann wird da eben nicht genau so viel länger, wie die Liste länger wurde, sondern nur im Verhältnis des Logarithmus von n. Und der Logarithmus, wenn du das noch aus der Mathematik kennst, das kann ich jetzt hier auf der Tonspur schwer erklären, wie man den ausrechnet, aber kannst einen Taschenrechner nehmen und da kommst du z.B. beim Logarithmus Basis zwei von 4 Milliarden auf irgendwas um den Dreh von zwei und dreiigste. Und ich mache es immer so, ich will das ja nicht mit dem Taschenrechner mal ausrechnen, so ganz grob überschlagen, wenn du so die Zweierpotenzen im Kopf durchgehst, da kannst du dich einigermaßen annähern. Z.B. 4 Milliarden sind halt zwei und dreiig Bit, 24 Bit sind irgendwas mit 16,7 Milliarden Millionen. Das heißt, wenn du irgendwie in einer Datenbank 8 Millionen Datensätze hast, könntest du mit dem nächsten Vielfachen von zwei der 16 zweitausendein Millionen. Das sind halt 24 Bit, ziehst du einen ab, hast du 23 Bit und das sind dann ungefähr 8 Millionen. Das heißt, wenn du 8 Millionen Datensätze durchsuchst mit einer binären Suche, dann brauchst du ungefähr 23 Suchvorgänge statt 8 Millionen. Das ist also ein sehr krasser Unterschied. So, jetzt haben wir alles zusammengebracht. Index ist im Prinzip einfach nur eine Liste, die sortiert ist, in der ich schneller suchen kann. Und zwar mit der binären Suche. Die hat eine Komplexität von O log n und das ist deutlich, deutlich schneller als die Komplexität der linearen Suche, nämlich O von N. Ja, das war es, glaube ich, eigentlich zum Thema Index. Kleinigkeit noch für die Praxis, denn Index ist jetzt nicht umsonst. Ich sage immer meinen Azubis in der IT, es ist alles immer ein Trade off, es gibt nichts umsonst. Und genauso ist beim Index, wenn ich einen Index auf jede Spalte in meiner Datenbank lege, dann ist das auch nicht zielführend, weil die Indizes sind ja nicht kostenfrei. Wir können uns das ganz einfach so vorstellen, dass wir eine zusätzliche Tabelle brauchen, wo dieser Index drin gespeichert wird. Und jedes Mal, wenn ich in meiner Originaltabelle Daten verändere, muss der Index natürlich angepasst werden. Wenn ich noch eine zweite Person einfüge, die Macke heißt, muss im Index ja der Schlüssel ergänzt werden unter dem Stichpunkt Macke. Das heißt, ich muss nicht nur in der einen Tabelle schreiben, sondern auch in meinem Index. Und wenn ich das jetzt auf jeder Spalte habe, einen Index, da muss ich ganz, ganz viele Indizes anpassen. Sobald ich ändernde Operationen auf meiner Tabelle mache, das wird dann extrem langsam. Plus ich habe natürlich einen deutlich höheren Speicherverbrauch, weil die Indizes enthalten ja genauso viele Datensätze, oder nicht genauso viele, aber maximal genauso viele Datensätze wie in der Ausgangstabelle. Das heißt, ich brauche natürlich auch mehr speicher Platz, um diesen Index ablegen zu können. Ja, das heißt, ich muss mir gut überlegen, guck mir meine Datenstruktur an, nach welchen Werten in meiner Relation Datenbank werde ich denn wahrscheinlich oft suchen? Oder ich werde die z.B. als Join Kriterium benutzen, wenn ich Select Abfragen habe und solche Dinge. Und auf diese Spalten sollte ich dann unbedingt einen Index legen, damit diese abfragen schneller werden. Übrigens, Primärschlüssel, Fremdschlüssel etc. Haben meistens automatisch einen Index. Primärschlüssel auf jeden Fall, da muss man sich also nicht drum kümmern, weil wenn ich nach dem Schlüssel in einer Tabelle ewig lange suchen müsste, dann könnte ich das Ding auch eine Textdatei schreiben. Gab es ja auch schon mal eine Episode zu im Engineering kiosk und gar keine Datenbank benutzen. Also irgendeinen Vorteil muss es ja haben. Und deswegen haben die Primärschlüssel automatisch einen Index drauf, damit ich schnell danach suchen kann. So, das war's zum Thema Index. Ganz einfach gesagt, eine umgedrehte Liste, die sortiert ist nach dem Suchbegriff und dann kann ich darüber mit einer logarithmischen Komplexität suchen, was deutlich schneller ist als mit der linearen Suche. Und das ist sowohl für die Prüfung interessant, wo man das gut erklären können darf, aber natürlich gerade auch für die Praxis. Also wenn du mit Datenbanken arbeitest, die keinen Index haben, ja dann viel Spaß. Dann wird es extrem langsam schon bei einer gar nicht mal so großen Menge an Daten, die da drin sind. Also nimm dir das auf jeden Fall mit und überleg dir gut, welche Spalten in deiner Datenbank einen Index brauchen. Das war's von mir hier im Engineering Kiosk. Ich hoffe, es war ein bisschen was Spannendes für dich dabei und ich wünsche dir ganz, ganz frohe Weihnachten. Und vielleicht hört man sich ja mal an anderer Stelle in einem Podcast wieder. Mach's gut. Tschüss.

Andy Grunwald (00:14:18 - 00:14:40)

Der Dank für diese Episode geht an Stefan. Vielen Dank. Hoffentlich hilft mir diese Episode beim Lösen des nächsten Advent of Code Rätsels. Wenn du mehr Fachwissen dieser Art von Stefan hören möchtest, schalte doch mal in seinen IT Berufe Podcast ein. Da geht es um alles, was du in den IT Fachinformatikerberufen brauchst. Den Link findest du natürlich in den Shows. Das war es von uns. Bis zum nächsten Adventskalendertürchen und tschüss.