Diskussion:Indexstruktur
Wäre es nicht sinnvoll, einen Satz zum einfachsten aller Indexe, der sortierten Liste, zu schreiben? Immerhin ist sie die Grundform aller Indexe?
- In wiefern soll eine sortierte Liste irgendeinen Vorteil gegenueber einer unsortierten haben? -- sparti 19:34, 26. Feb. 2007 (CET)
- Sie erlaubt den Abbruch der Suche. Suche ich nach "B", kann ich bei "C" aufhören. Habe ich eine Liste mit Random Access, so kann ich eine Binäre Suche durchführen, das ist schon ziemlich effizient. Also ja, auch eine sortierte Liste ist ein Index. Updates sind leider nicht so praktisch ... Ich finde aber das klassische Karteikasten-Beispiel viel besser. Ist für jeden leicht nachvollziehbar. --Chire 13:02, 16. Mai 2010 (CEST)
- Binäre Suche hat einen eigenen Artikel, eigentlich reicht es, wenn es dort beschrieben ist ... --Chire 18:16, 28. Jun. 2010 (CEST)
- P.S. Eigentlich jedes Telefonbuch das ich kenne ist nach Anfangsbuchstabe "gruppiert"; den vergleich mit einer binären Suche finde ich daher nicht so optimal. Ein von Hand angelegtes Telefonbuch wird man auch nie als sortierte Liste pflegen, da man da i.d.R. nicht Einfügen kann. Ich suche auch keineswegs binär im Sinne dass ich die Mitte aufschlagen würde, sondern ich versuche bereits abzuschätzen wo der Eintrag sein könnte. Sprich, wenn ich "Bauer" suche, fange ich nicht in der Mitte an, sondern vielleicht bei 5%. Ich finde daher dein Beispiel nicht überzeugend. Das Geburtstagslisten-Beispiel finde ich aber eine gute Ergänzung zu dem bestehenden Karteikarten-System: in den Geburtstagskalender schreibt man nur die Namen, nicht die Adressen. --Chire 18:10, 1. Jul. 2010 (CEST)
- Ja, jedes Beispiel hinkt ein bisschen. Der Mensch interpoliert natürlich und schätzt ab, dass der Buchstabe "B" nicht in der Mitte des Alphabets steht, sondern ziemlich am Anfang. Aber das Verhältnis 2/26 könnte man in die binäre Suche auch noch einbauen. Aber ich denke mir, man macht es nicht, weil der Algorithmus so brutal gut konvergiert, dass es auf das gar nicht mehr ankommt. Man sollte den Algorithmus gar nicht "Binäre Suche", sondern vielleicht "Binäre Entscheidung" oder "Binäre Berechnung" nennen, denn mit Suche hat das ja fast nichts mehr zu tun und "Suche" klingt ein bisschen so, als würde im Vergleich zur Suche in einer unsortierten Liste keine Verbesserung stattfinden. Das Sortieren ist schon ein geniales Konzept. Überleg nur mal, dass ein Mensch überhaupt in der Lage ist, im Telefonbuch einer Großstadt einen Namen nachzuschlagen... Mach das mal mit einem unsortierten Telefonbuch... Ich habe auch schon mal ein Adressbuch nach Anfangsbuchstaben indiziert. Bis zum dritten Buchstaben zu indizieren ist sicherlich ein sinnvoller Wert. Aber dann stellt man fest, dass viele Namen mit "Sch" beginnen und an diesen drei Buchstaben die ganze Energie verpufft, und dann ersetzt man das "Sch" durch ein Sonderzeichen, um das zu vermeiden, und dann ist man so langsam reif fürs Sortieren und die binäre Suche (ist aber sicherlich auch ein bisschen Geschmacksache). (nicht signierter Beitrag von Bernhard.B.59 (Diskussion | Beiträge) 11:10, 2. Jul 2010 (CEST)) Sorry, signiere hiermit nachträglich--Bernhard.B.59 12:55, 5. Jul. 2010 (CEST)
- Habe ein paar formale Kleinigkeiten an deiner Ausarbeitung geändert --Bernhard.B.59 13:13, 5. Jul. 2010 (CEST)
- Danke! Insbesondere für die Idee mit den Geburtstagen. Gerade die Kombination Adresskartei + Geburtstagsliste ist denke ich wirklich Oma-geeignet. --Chire 13:51, 5. Jul. 2010 (CEST)
- Habe ein paar formale Kleinigkeiten an deiner Ausarbeitung geändert --Bernhard.B.59 13:13, 5. Jul. 2010 (CEST)
- Ja, jedes Beispiel hinkt ein bisschen. Der Mensch interpoliert natürlich und schätzt ab, dass der Buchstabe "B" nicht in der Mitte des Alphabets steht, sondern ziemlich am Anfang. Aber das Verhältnis 2/26 könnte man in die binäre Suche auch noch einbauen. Aber ich denke mir, man macht es nicht, weil der Algorithmus so brutal gut konvergiert, dass es auf das gar nicht mehr ankommt. Man sollte den Algorithmus gar nicht "Binäre Suche", sondern vielleicht "Binäre Entscheidung" oder "Binäre Berechnung" nennen, denn mit Suche hat das ja fast nichts mehr zu tun und "Suche" klingt ein bisschen so, als würde im Vergleich zur Suche in einer unsortierten Liste keine Verbesserung stattfinden. Das Sortieren ist schon ein geniales Konzept. Überleg nur mal, dass ein Mensch überhaupt in der Lage ist, im Telefonbuch einer Großstadt einen Namen nachzuschlagen... Mach das mal mit einem unsortierten Telefonbuch... Ich habe auch schon mal ein Adressbuch nach Anfangsbuchstaben indiziert. Bis zum dritten Buchstaben zu indizieren ist sicherlich ein sinnvoller Wert. Aber dann stellt man fest, dass viele Namen mit "Sch" beginnen und an diesen drei Buchstaben die ganze Energie verpufft, und dann ersetzt man das "Sch" durch ein Sonderzeichen, um das zu vermeiden, und dann ist man so langsam reif fürs Sortieren und die binäre Suche (ist aber sicherlich auch ein bisschen Geschmacksache). (nicht signierter Beitrag von Bernhard.B.59 (Diskussion | Beiträge) 11:10, 2. Jul 2010 (CEST)) Sorry, signiere hiermit nachträglich--Bernhard.B.59 12:55, 5. Jul. 2010 (CEST)
Mehrdimensionale Indexstrukturen
Ich werde mir den Abschnitt demnächst mal vornehmen, denn er macht so keinen Sinn. Ein Index ist in dem Moment Mehrdimensional, wo er mehr als ein Attribut indiziert. z.B. Kartendaten, indiziert nach Abstand. Ich werde nie eine Tankstelle nach ihrem Breitengrad alleine suchen, sondern eher die "nächstgelegene" Tankstelle, wozu ich beide brauche. Was hier derzeit beschrieben wird, sind Indexstrukturen, die Anfragen nach *Unterräumen* erlauben. Das kann in vielen Strukturen über Bereichsanfragen emuliert werden; Abstandsanfragen klappen dann meist schon nicht mehr so toll. --Chire 13:02, 16. Mai 2010 (CEST)
"Teile und Herrsche" entfernt
Ich habe diesen Verweis (im Abschnitt "Funktionsbeispiel") entfernt. Hier eine kurze Begründung: Teile und Herrsche bezeichnet den Trick, ein großes Problem in mehrere kleine, einfachere Teilprobleme zu zerlegen, anschließend diese alle zu lösen, und dann das Ergebnis zu rekombinieren. Bei der Suche nach einem Namen in einem Karteikartensystem passiert dies aber nicht, und auch die meisten Indexstrukturen machen das nicht - im Gegenteil. Das Ziel einer Indexstruktur ist es, möglichst große Teile ausschließen zu können (Englisch: "pruning"). Insbesondere, um sie nicht von der Platte laden zu müssen. Teile und Herrsche impliziert eine Art Symmetrie in den Teilen, während hier alle Teile bis auf einen trivial sind.
Natürlich ist Teile und Herrsche nicht irrelevant - den gerade beim Aufbau einer Indexstruktur wird es oft verwendet, z.B. beim Sortieren. --Chire 13:26, 16. Mai 2010 (CEST)
- In der Tat wird die Binäre Suche teilweise als Divide & Conquer bezeichnet; der Absatz war trotzdem etwas komisch platziert. Und das tpyische Prinzip von Indexstrukturen ist eigentlich nur das Teilen, beherrscht wird eben gar nicht viel. --Chire 14:49, 16. Mai 2010 (CEST)
