Wieviele Blöcke werden für einen (flachen) dense Index auf R benötigt.

[Smoketm]

Hallo Leute,

Mir ist nicht ganz klar, wie ich bei dieser Aufgabe vorgehen muss.

Ein Block kann 500 Index-Einträge oder 80 Datensätze der Relation R speichern. R enthält 10.000.000 Datensätze.

a) Wieviele Blöcke werden für einen (flachen) dense Index auf R benötigt.
b) Wieviele Blöcke werden für einen (flachen) sparse Index auf R benötigt, der einen Eintrag pro Block der Daten Datei enthält.

Für a) muss ich erst einmal berechnen wie viele Blöcke es sind. Also 10.000.000/80 = 125 000
Aber was ich jetzt machen muss mit dense Index keine Ahnung kann mir darunter nicht wirklich was vorstellen.

LG

 

[akretschmer]

vermutlich suchst Du das als Erklärung:

https://www.quora.com/What-is-the-difference-between-sparse-index-and-dense-index
Difference between sparse index and dense index

Das dürfte dann auch Deine Fragen erklären.

 

[Smoketm]

Jetzt muss ich dazu noch etwas Fragen. Das heißt für jedes Tupel in R gibt es einen Index-Eintrag bei a), aber was hat das mit den Blöcken zu tun? Es befindet sich in allen Blöcken ?
Das heißt ich brauche 125000 Blöcke bei a)?

Das wäre wahrscheinlich zu einfach

 

[akretschmer]

Nehmen wir mal PostgreSQL. Ein Block sind 8KB. In einem 'normalen' Index ist jeder Eintrag in der Tabelle auch ein Intrag im Index. Wenn Du 10.000.000 Datensätze hast, brauchst Du im Index auch 10.000.000 Einträge, 500 passen in einen Block. Die Größe des Indexes ist nun klar, oder?

Dann gibt es BRIN-Indexe (Block Range Index, vermutlich das, was hier als b gemeint ist) Bei Einem BRIN-Index ist nicht mehr 1:1 ein Eintrag im Index für jeden Tupel in der Tabelle, sondern nur noch je Block der Tabelle ein Eintrag mit MIN und MAX - Wert, den es in der Tabelle je Block gibt.

Beispiel: eine Tabelle mit Log-Einträgen. Im ersten Block stehen Einträge vom 1.1.2017 bis 14.1.2017, im zweiten Block vom 14.1. bis 20.1.2017. Im BRIN-Index wären nun zwei Einträge, der erst sagt, Daten vom 1.1. bis 14.1. stehen im Block 1 der Tabelle, Daten vom 14.1. bis 20.1. im Block 2. Suche ich nach Daten vom 5.1. wüste ich aus dem Index, daß ich Block 1 der Tabelle brauche, suche ich nach dem 19. brauche ich nur Block 2 und suche ich nach dem 14. müßte ich in Block 1 und 2 der Tabelle suchen. Ich habe also zwar hunderte von Datensätzen in der Tabelle, aber nur 2 kleine Einträge im Index. Nachteil: ich habe keinen genauen Zeiger auf die Tabelle, ich weiß nur, ich muß in dem/den Blöcken suchen. BRIN-Indexe sind also ungenauer und damit langsamer, aber sehr viel kleiner. Selbst bei mehrstelligen TB-großen Tabellen sind solche Indexe nur ein paar MB groß und passen damit in den RAM. Ein 'normaler' Index wäre um etliche Zehnerpotenzen größer.

 

[Smoketm]

Mhm ok a) ist klar, aber bei b) blick ich immer noch nicht ganz durch. "Der einen Eintrag pro Block der Daten Datei enthält", dass bedeutet das kann ich doch nur bestimmen, wenn ich weiß wieviele gleiche Suchschlussel vorkommen? Die müssen ja noch dazu geordnet sein? Ich meine damit ich muss es irgendwie schaffen die Relation R in Blöcke zu unterteilen.

 

[akretschmer]

b) habe ich Dir via BRIN versucht zu erklären. Unabhängig davon, wie viele Einträge in einem Block der Tabelle sind, ist im Index nur die Information über MIN und MAX. Ich weiß nicht, welche DB am Start ist, vermutlich kein PostgreSQL. Ergründe also, was das für eine DB ist, und suche in dessen Doku, wie dieser Index funktioniert. Das kann, muß aber nicht, ähnlich zu BRINunter PostgreSQL sein.

 

[Smoketm]

Doch soweit ich weiß richten wir uns nach der Postgres Doku. Die Erklärung von dir war super, nur weiß ich eben nicht wieviele Einträge ich pro Block habe, dazu müsste ich wissen wieviele gleiche Suchschlüssel es gibt ? Falls ich das richtig verstanden habe.

 

[akretschmer]

Bei BRIN sind je Block im Index exakt 2 Einträge, diese definieren MIN und MAX - Wert der Spalte in diesem Block. Also im Prinzip:

Blocknummer:MIN:MAX

Oder für mein Beispiel:

1:01.01.2017:14.01.2017
2:14.01.2017:20.01.2017

 

[Smoketm]

Ok das müsste dann für mein Beispiel heißen es gibt nur 2 Einträge pro Block also immer nur min und max, wobei zwischen min und max nichts vorhanden ist da ja min und max aufeinanderfolgt also 1 und 2 zb.

 

[akretschmer]

jepp.