Dagens kort – Database cracking og adaptiv indeksering

Kort 1 av 100%

Database cracking og adaptiv indekseringmedium

Hva er I/O-kostnaden for den første og den $q$ -te spørringen med cracking ( $n$ elementer)?

Klikk for å snu kortet

Database cracking og adaptiv indekseringSvar

Første spørring: $O(n)$ – full lineær scan for partisjonering. Etter $q$ overlappende spørringer: amortisert $O(n/q)$ per spørring. Total konvergenskostnad: $O(n \log n)$ sammenligninger.

Space / Enter for å snu