ZSBD-2st-1.2-w6.tresc-1.1-Slajd12

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zarządzanie dużymi obiektami

Zarządzanie dużymi obiektami


Rozmiar dużych obiektów może być na tyle duży, że istotne staje się wydajne zarządzanie pojedynczymi dużymi obiektami. Dla dużych obiektów należy zagwarantować wydajną realizację operacji wyszukiwania, wstawiania, modyfikacji i usuwania sekwencji bajtów o określonej długości i lokalizacji w strukturze obiektu rozumianej jako ciąg bajtów.

Wydajna implementacja dużych obiektów opiera się na dwóch istotnych założeniach. Po pierwsze zapewnienia wydajnej metody wyszukiwania w ciągu bajtów rozrzuconych po wszystkich stronach dyskowych dużego obiektu bajtu o numerze określającym jego pozycję w ciągu bajtów. Po drugie zagwarantowania, że lokalne modyfikacje obiektu będą wymagały jedynie lokalnej rekonstrukcji jego struktury.

Jednym z rozwiązań wydajnej implementacji dużych obiektów jest ich organizacja w postaci rzadkiego indeksu o strukturze B-drzewa. Atrybutem na którym jest zakładany taki indeks jest numer pozycji danego bajtu w ciągu wszystkich bajtów składających się na duży obiekt. Liśćmi indeksu są strony dyskowe składające się na duży obiekt. Węzły wewnętrzne indeksu nie przechowują zawartości obiektu, lecz służą do wyszukiwanie bajtów o określonej lokalizacji. Dla zagwarantowania wydajności operacji modyfikacji wypełnienie stron dyskowych nie jest maksymalizowane. Tak jak w zwykłych B-drzewach algorytmy utrzymania indeksu gwarantują wypełnienie liści w granicach od 50 do 100%. Dzięki temu operacje powiększania dużego obiektu przez wstawienie w określonej pozycji nowego podciągu bajtów lub usunięcie z obiektu podciągu o określonej pozycji i długości, wymagają jedynie lokalnych rekonstrukcji ograniczonej liczby stron dyskowych.

Opisywana struktura została zilustrowana na slajdzie. Przedstawiony duży obiekt składa się z sześciu stron dyskowych. Maksymalny rozmiar stron to 512 bajtów. Strony te zawierają kolejne fragmenty całego obiektu o długościach odpowiednio: 450, 500, 379, 400, 510 i 496 bajtów. Dwa wyższe poziomy indeksu składają się z trzech węzłów wewnętrznych. Na slajdzie pokazano operację wyszukiwania pojedynczego bajtu, który jest 1800 bajtem obiektu. W korzeniu indeksu pozycja ta jest przeliczona na pozycję w prawym poddrzewie indeksu. Lewe poddrzewo indeksuje bajty począwszy od 1 do 1329. Stąd względna pozycja szukanego bajtu w prawym poddrzewie jest różnicą bezwzględnej pozycji szukanego bajtu: n=1800 i liczby bajtów znajdujących się w lewym poddrzewie. Przeliczone względna pozycja w prawym poddrzewie jest równa n’=461. Z kolejnego przeliczenia w prawym węźle wewnętrznym drugiego poziomu wynika, że poszukiwany bajt jest 61 bajtem piątej strony dyskowej całego obiektu.


<< Poprzedni slajd | Spis treści | Następny slajd >>