Jak bazy danych przechowują wartości kluczy indeksu (na dysku) dla pól o zmiennej długości?

Kontekst

To pytanie dotyczy szczegółów implementacji indeksów niskiego poziomu w systemach baz danych SQL i NoSQL. Rzeczywista struktura indeksu (drzewo B +, skrót, SSTable itp.) Jest nieistotna, ponieważ pytanie dotyczy konkretnie kluczy przechowywanych w jednym węźle dowolnej z tych implementacji.

tło

W bazach danych SQL (np. MySQL) i NoSQL (CouchDB, MongoDB itp.), Gdy budujesz indeks na polu danych kolumny lub dokumentu JSON, tak naprawdę powoduje to, że baza danych tworzy zasadniczo posortowaną listę wszystkich wartości te wraz z przesunięciem pliku do głównego pliku danych, w którym znajduje się rekord dotyczący tej wartości.

(Dla uproszczenia mogę ręcznie wymachiwać innymi ezoterycznymi szczegółami konkretnych implantów)

Prosty klasyczny przykład SQL

Rozważmy standardową tabelę SQL z prostym 32-bitowym kluczem podstawowym int, na którym tworzymy indeks, skończymy z indeksem na dysku kluczy całkowitych posortowanych i skojarzonych z 64-bitowym przesunięciem do pliku danych, w którym płyta żyje, np .:

id   | offset
--------------
1    | 1375
2    | 1413
3    | 1786

Przedstawienie na dysku kluczy w indeksie wygląda mniej więcej tak:

[4-bytes][8-bytes] --> 12 bytes for each indexed value

Trzymając się podstawowych zasad optymalizacji optymalizacji I / O dysku za pomocą systemów plików i systemów baz danych, załóżmy, że przechowujesz klucze w blokach 4KB na dysku, co oznacza:

4096 bytes / 12 bytes per key = 341 keys per block

Ignorując ogólną strukturę indeksu (B + drzewo, skrót, posortowana lista itp.), Odczytujemy i zapisujemy bloki 341 kluczy naraz w pamięci i w razie potrzeby z powrotem zapisujemy na dysk.

Przykładowe zapytanie

Korzystając z informacji z poprzedniej sekcji, powiedzmy, że pojawia się zapytanie o „id = 2”, klasyczne wyszukiwanie indeksu DB wygląda następująco:

1. Przeczytaj katalog główny indeksu (w tym przypadku 1 blok)
2. Przeszukaj binarnie posortowany blok, aby znaleźć klucz
3. Uzyskaj przesunięcie pliku danych od wartości
4. Wyszukaj rekord w pliku danych, używając przesunięcia
5. Zwróć dane dzwoniącemu

Konfiguracja pytania ...

Ok, tutaj pojawia się pytanie ...

Krok # 2 jest najważniejszą częścią, która pozwala na wykonanie tych zapytań w czasie O (logowania) ... informacje muszą być posortowane, ALE musisz być w stanie przeglądać listę w szybki sposób ... więcej w szczególności musisz być w stanie przeskoczyć do dobrze zdefiniowanych przesunięć do woli, aby odczytać wartość klucza indeksu w tej pozycji.

Po przeczytaniu w bloku musisz być w stanie natychmiast skoczyć na 170. pozycję, przeczytać kluczową wartość i zobaczyć, czy to, czego szukasz, to GT lub LT tej pozycji (i tak dalej itd.)

Jedynym sposobem, w jaki możesz przeskakiwać dane w bloku w ten sposób, jest to, że wszystkie wielkości wartości klucza są dobrze zdefiniowane, tak jak w naszym przykładzie powyżej (4 bajty, a następnie 8 bajtów na klucz).

PYTANIE

Ok, więc tutaj utknąłem z wydajnym projektowaniem indeksów ... dla kolumn varchar w bazach SQL, a dokładniej, całkowicie dowolnych pól w bazach dokumentów takich jak CouchDB lub NoSQL, gdzie dowolne pole, które chcesz indeksować, może być dowolne długość w jaki sposób wdrażasz kluczowe wartości, które są wewnątrz bloków struktury indeksu, z których budujesz swoje indeksy?

Załóżmy na przykład, że używasz sekwencyjnego licznika dla identyfikatora w CouchDB i indeksujesz tweety ... po kilku miesiącach będziesz mieć wartości od „1” do „100 000 000 000”.

Załóżmy, że budujesz indeks na bazie danych w dniu 1, gdy w bazie danych są tylko 4 tweety, CouchDB może ulec pokusie użycia następującej konstrukcji kluczowych wartości w blokach indeksu:

[1-byte][8-bytes] <-- 9 bytes
4096 / 9 = 455 keys per block

W pewnym momencie to się psuje i potrzebujesz zmiennej liczby bajtów, aby zapisać wartość klucza w indeksach.

Problem jest jeszcze bardziej rażący, jeśli zdecydujesz się zaindeksować pole o naprawdę zmiennej długości, takie jak „tweet_message” lub coś w tym rodzaju.

Ponieważ sam klucz ma całkowitą zmienną długość, a baza danych nie ma możliwości inteligentnego odgadnięcia „maksymalnego rozmiaru klucza” podczas tworzenia i aktualizacji indeksu, w jaki sposób klucze są faktycznie przechowywane w blokach reprezentujących segmenty indeksów w tych bazach danych ?

Oczywiście, jeśli klucze są zmienne wielkości i można przeczytać w bloku klawiszy, nie tylko nie masz pojęcia, jak wiele klucze są rzeczywiście w bloku, ale nie masz pojęcia, jak skakać na środku listy, aby zrobić binarny szukaj na nich.

To tutaj zaczynam się potykać.

W przypadku pól o typie statycznym w klasycznych bazach danych SQL (takich jak bool, int, char itp.) Rozumiem, że indeks może po prostu wstępnie zdefiniować długość klucza i trzymać się jej ... ale w tym świecie magazynów danych dokumentów jestem zakłopotany tym, jak wydajnie modelują te dane na dysku, aby można je było skanować w czasie O (logowania) i docenilibyśmy tutaj wszelkie wyjaśnienia.

Daj mi znać, jeśli potrzebne będą jakieś wyjaśnienia!

Aktualizacja (odpowiedź Grega)

Proszę zobaczyć moje komentarze dołączone do odpowiedzi Grega. Po tygodniu dalszych badań wydaje mi się, że naprawdę natknął się na cudownie prostą i wydajną sugestię, że w praktyce jest bardzo łatwa do wdrożenia i użycia, a jednocześnie zapewnia dużą wydajność, unikając deserializacji kluczowych wartości, na których ci nie zależy.

Przyjrzałem się 3 oddzielnym implementacjom DBMS (CouchDB, kivaloo i InnoDB) i wszystkie one rozwiązują ten problem, deserializując cały blok do wewnętrznej struktury danych przed przeszukaniem wartości w środowisku wykonawczym (erlang / C).

To, co myślę, jest tak genialne w sugestii Grega; normalny rozmiar bloku 2048 normalnie miałby 50 lub mniej przesunięć, co skutkowałoby bardzo małym blokiem liczb, który musiałby zostać wczytany.

Aktualizacja (potencjalne wady sugestii Grega)

Aby jak najlepiej kontynuować ten dialog ze sobą, zdałem sobie sprawę z następujących wad tego ...

1. Jeśli do każdego „bloku” dołączone są dane przesunięcia, nie można pozwolić na dostosowanie rozmiaru bloku w konfiguracji później, ponieważ może to spowodować odczyt danych, które nie zaczynają się poprawnie od nagłówka lub bloku, który zawiera wiele nagłówków.

2. Jeśli indeksujesz ogromne wartości kluczy (powiedzmy, że ktoś próbuje zaindeksować kolumnę char (8192) lub blob (8192)), możliwe jest, że klucze nie mieszczą się w jednym bloku i muszą zostać przepełnione przez dwa bloki obok siebie . Oznacza to, że pierwszy blok miałby przesunięty nagłówek, a drugi blok natychmiast zaczynałby się od kluczowych danych.

Rozwiązaniem tego wszystkiego jest ustalony rozmiar bloku bazy danych, który nie jest regulować, i tworzenie wokół niego struktur danych bloku nagłówka ... na przykład, naprawiasz wszystkie rozmiary bloków do 4KB (zazwyczaj najbardziej optymalne i tak) i piszesz bardzo mały nagłówek bloku, który zawiera na początku „typ bloku”. Jeśli jest to normalny blok, to bezpośrednio po nagłówku bloku powinien znajdować się nagłówek przesunięć. Jeśli jest to typ „przepełnienia”, to bezpośrednio po nagłówku bloku znajdują się dane surowego klucza.

Aktualizacja (potencjalnie niesamowity wzrost)

Po wczytaniu bloku jako serii bajtów i dekodowaniu przesunięć; technicznie możesz po prostu zakodować szukany klucz do surowych bajtów, a następnie dokonać bezpośrednich porównań w strumieniu bajtów.

Po znalezieniu szukanego klucza wskaźnik można zdekodować i śledzić.

Kolejny niesamowity efekt uboczny pomysłu Grega! Potencjał optymalizacji czasu procesora tutaj jest na tyle duży, że ustawienie stałego rozmiaru bloku może być tego warte, aby to wszystko uzyskać.

Możesz przechowywać swój indeks jako listę przesunięć o stałym rozmiarze w bloku zawierającym twoje kluczowe dane. Na przykład:

+--------------+
| 3            | number of entries
+--------------+
| 16           | offset of first key data
+--------------+
| 24           | offset of second key data
+--------------+
| 39           | offset of third key data
+--------------+
| key one |
+----------------+
| key number two |
+-----------------------+
| this is the third key |
+-----------------------+

(cóż, kluczowe dane zostałyby posortowane na prawdziwym przykładzie, ale masz pomysł).

Zauważ, że niekoniecznie odzwierciedla to faktyczną konstrukcję bloków indeksów w dowolnej bazie danych. To jest jedynie przykładem, w jaki sposób można zorganizować blok danych indeksowych gdzie kluczowe dane o zmiennej długości.