Wykład 7. Indeksy.pdf

Bazy danych - BD

Indeksy

Wykład przygotował:

Robert Wrembel

BD – wykład 7 (1)

Bazy danych - BD

Plan wykładu

• Problematyka indeksowania

• Podział indeksów i ich charakterystyka

– indeks podstawowy, zgrupowany, wtórny

– indeks rzadki, gęsty

• Indeks wielopoziomowy statyczny (ISAM)

• Indeks wielopoziomowy dynamiczny (B + -drzewo)

• Algorytm wstawiania danych do indeksu B + -drzewo

BD – wykład 7 (2)

Celem wykładu jest omówienie podstawowych koncepcji indeksowania danych i struktur

indeksowych. W ramach wykładu zostaną omówione:

- wprowadzenie do problematyki indeksowania danych,

- charakterystyka różnego rodzaju indeksów (podstawowy, zgrupowany, wtórny, rzadki i

gęsty),

- indeks wielopoziomowy statyczny (ISAM),

- indeks wielopoziomowy dynamiczny (B + -drzewo),

- algorytm wstawiania danych do indeksu B + -drzewo.

Bazy danych - BD

Wprowadzenie (1)

• Problem:

– Dany jest plik zawierający uporządkowane lub

nieuporządkowane rekordy danych

– W jaki sposób efektywnie zrealizować wyszukanie

rekordu lub rekordów z zadanego zakresu wartości

wybranego pola?

BD – wykład 7 (3)

Rozważmy plik zawierający uporządkowane lub nieuporządkowane rekordy danych. Jak

pamiętamy z poprzedniego wykładu wyszukiwanie danych w plikach nie jest efektywne.

Z tego względu chcielibyśmy znaleźć sposób efektywnego wyszukiwania danych.

Bazy danych - BD

Wprowadzenie (2)

• Odpowiedź:

–Utworzyć drugi plik, zdefiniowany na atrybucie

wykorzystanym do specyfikacji kryterium

poszukiwania

– Plik ten zawiera rekordy odpowiadające

poszukiwanym wartościom pierwszych rekordów w

poszczególnych blokach pliku danych

– Rekordy w dodatkowym pliku mają postać:

– Plik dodatkowy jest uporządkowany według wartości

poszukiwanych

BD – wykład 7 (4)

Rozwiązanie tego problemu bazuje na wykorzystaniu drugiego pliku zdefiniowanego na

atrybucie wykorzystanym do specyfikowania kryterium przeszukiwania. Plik ten

zawierałby rekordy odpowiadające poszukiwanym wartościom pierwszych rekordów w

poszczególnych blokach pliku danych. Rekordy w dodatkowym pliku miałyby postać:

<pierwszy klucz w bloku, wskaźnik do bloku>, a plik dodatkowy byłby uporządkowany

według wartości poszukiwanych.

Taki plik dodatkowy nazywa się indeksem.

Bazy danych - BD

Wprowadzenie (3)

• Indeks - dodatkowa struktura fizyczna

• Cel stosowania - przyśpieszenie dostępu do danych

•Zakładane na pojedynczych atrybutach lub zbiorach

atrybutów relacji

– atrybuty te są nazywane indeksowymi

• Model fizyczny indeksu

– uporządkowany plik rekordów indeksu (ang. data

entry) o stałej długości

– rekord indeksu zawiera dwa pola

•klucz reprezentujący jedną z wartości

występujących w atrybutach indeksowych relacji

• wskaźnik do bloku danych zawierający krotkę,

której atrybut indeksowy równy jest kluczowi

BD – wykład 7 (5)

Indeks zdefiniowany na pliku jest dodatkową strukturą fizyczną, której celem jest

przyspieszenie wykonywania operacji, które nie są wystarczająco efektywnie wspierane

przez podstawowe organizacje plików i struktury logiczne danych.

Indeksy są zakładane na pojedynczych atrybutach lub zbiorach atrybutów relacji.

Atrybuty te noszą nazwę atrybutów indeksowych.

Indeks jest uporządkowanym plikiem rekordów indeksu (ang. data entry) o stałej

długości. Rekordy indeksu zawierają dwa pola: klucz reprezentujący jedną z wartości

występujących w atrybutach indeksowych relacji oraz wskaźnik do bloku danych

zawierający krotkę, której atrybut indeksowy równy jest kluczowi.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: