W jakiej kolejności należy wstawić zestaw znanych kluczy do drzewa B, aby uzyskać minimalną wysokość?

Question

Biorąc pod uwagę stałą liczbę kluczy lub wartości (przechowywanych w tablicy lub w jakiejś strukturze danych) i kolejność b-drzewa, możemy określić kolejność wstawiania kluczy, które wygenerowałyby efektywne przestrzennie drzewo b.

Aby to zilustrować, rozważ b-tree rzędu 3. Niech klucze będą {1,2,3,4,5,6,7}. Wstawianie elementów w drzewie w następującej kolejności

for(int i=1 ;i<8; ++i) 
{ 
tree.push(i); 
} 

by utworzyć drzewo takiego

 4 
    2  6 
    1 3 5 7 

zobaczyć http://en.wikipedia.org/wiki/B-tree

Ale wstawianie elementów w ten sposób

flag = true; 
for(int i=1,j=7; i<8; ++i,--j) 
{ 
    if(flag) 
    { 
     tree.push(i); 
     flag = false; 
    } 
    else 
    { 
     tree.push(j); 
     flag = true; 
    } 
} 

tworzy drzewo tak to

3 5 
1 2 4 6 7 

gdzie widzimy, że jest spadek poziomu.

Czy istnieje szczególny sposób określania sekwencji wstawiania, która zmniejszyłaby zużycie przestrzeni?

Answer 1

Niestety, wszystkie drzewa mają najgorszy możliwy scenariusz i wymagają sztywnych technik równoważenia, gdy dane są wprowadzane w porządku rosnącym. Drzewa binarne szybko zamieniają się w powiązane listy, itp.

Dla typowych przypadków użycia B-Tree (bazy danych, systemy plików itp.), Można zwykle liczyć na to, że dane będą naturalnie bardziej rozproszone, tworząc drzewo bardziej jak twój drugi przykład.

Chociaż może to być naprawdę niepokojące, można zaszyfrować każdy klucz, gwarantując szerszy rozkład wartości.

for(i=1; i<8; ++i) 
    tree.push(hash(i)); 

Answer 2

Poniższa sztuczka powinna działać na większości zamówionych wyszukiwania drzew, zakładając, że dane do wstawienia są liczbami całkowitymi 1..n.

Rozważmy binarną reprezentację kluczy integer - dla 1..7 (z kropkami dla zer), który jest ...

Bit : 210 
    1 : ..1 
    2 : .1. 
    3 : .11 
    4 : 1.. 
    5 : 1.1 
    6 : 11. 
    7 : 111 

bit 2 zmiany najrzadziej, bit 0 Zmiany najczęściej. To przeciwieństwo tego, co chcemy, więc co, jeśli odwrócić kolejność tych bitów, a następnie posortować klucze w kolejności tej wartości bitów odwrócony ...

Bit : 210 Rev 
    4 : 1.. -> ..1 : 1 
    ------------------ 
    2 : .1. -> .1. : 2 
    6 : 11. -> .11 : 3 
    ------------------ 
    1 : ..1 -> 1.. : 4 
    5 : 1.1 -> 1.1 : 5 
    3 : .11 -> 11. : 6 
    7 : 111 -> 111 : 7 

Najłatwiej wyjaśnić to w kategoriach niezbilansowane drzewo wyszukiwania binarnego, rosnące przez dodanie liści. Pierwszy element to martwy środek - dokładnie taki przedmiot chcemy dla korzenia. Następnie dodajemy klucze do następnej warstwy. Na koniec dodajemy warstwę liści. Na każdym kroku drzewo jest tak zrównoważone, jak to tylko możliwe, więc nawet jeśli budujesz drzewo AVL lub zrównoważone czerwono-czarne drzewo, logika równoważenia nie powinna być nigdy przywoływana.

[EDIT Po prostu zdałem sobie sprawę, że nie trzeba sortować danych w oparciu o wartości odwróconych bitów, aby uzyskać dostęp do kluczy w tej kolejności. Sztuką tego jest zauważenie, że odwracanie bitów jest jego własną odwrotnością. Oprócz mapowania klawiszy do pozycji, mapuje pozycje do klawiszy. Więc jeśli przełączysz się z 1 ...n, możesz użyć tej wartości odwróconej bitem, aby zdecydować, który element wstawić jako następny - dla pierwszej wstawki użyj czwartego elementu, dla drugiej wkładki użyj drugiego elementu i tak dalej. Jedna komplikacja - musisz zaokrąglić n do góry do jednego mniej niż potęga dwóch (7 jest OK, ale użyj 15 zamiast 8) i musisz ograniczyć-sprawdź wartości odwróconych bitów. Powodem jest to, że bit-cofania może przenieść niektóre z aut pozycji out-of-granicach i na odwrót.]

Faktycznie, na drzewo czerwono-czarne niektóre logika zrównoważenie zostanie wywołany, ale powinno to być po prostu ponownie kolorując węzły - nie zmieniając ich. Jednak nie poddałem się podwójnej kontroli, więc nie polegaj na tym roszczeniu.

Dla drzewa B wysokość drzewa rośnie, dodając nowy root. Udowodnienie tych prac jest więc trochę niezręczne (i może wymagać bardziej ostrożnego podziału węzłów, niż zwykle wymaga tego drzewo B), ale podstawowa idea jest taka sama. Chociaż występuje ponowne równoważenie, występuje ono w sposób zrównoważony z powodu kolejności wstawień.

Można to uogólnić na dowolny zestaw kluczy znanych z wyprzedzeniem, ponieważ po posortowaniu kluczy można przypisać odpowiednie indeksy na podstawie sortowanej kolejności.

---

UWAGA - To nie jest skutecznym sposobem na zbudowanie doskonale wyważone drzewo ze znanych już posortowanych danych.

Jeśli masz już posortowane dane i znasz ich wielkość, możesz zbudować idealnie zbalansowane drzewo w czasie O (n). Oto niektóre Pseudokod ...

if size is zero, return null 
from the size, decide which index should be the (subtree) root 
recurse for the left subtree, giving that index as the size (assuming 0 is a valid index) 
take the next item to build the (subtree) root 
recurse for the right subtree, giving (size - (index + 1)) as the size 
add the left and right subtree results as the child pointers 
return the new (subtree) root 

Zasadniczo, to decyduje o strukturze drzewa na podstawie rozmiaru i przemierza tę strukturę, budowę rzeczywiste węzłów po drodze. Nie powinno być zbyt trudno przystosować go do drzewek B.

Answer 3

Aby zbudować konkretne drzewo B przy użyciu funkcji Wstaw() jako czarnej skrzynki, należy wykonać czynność wstecz. Biorąc pod uwagę niepuste drzewo B, znajdź węzeł z minimalną liczbą dzieci najbliżej liści. Uważa się, że root ma minimum 0, więc węzeł z minimalną liczbą dzieci zawsze istnieje. Usuń wartość z tego węzła, która ma być uprzednio dodana do listy wywołań funkcji Insert(). Pracuj w kierunku liści, łącząc poddrzewienia.

Na przykład, biorąc pod uwagę 2-3 drzewo

 8 
    4  c 
2 6 a e 
1 3 5 7 9 b d f, 

zdecydujemy 8 i zrobić scala uzyskanie poprzednika

4  c 
2 6 a e 
1 3 5 79 b d f. 

Wtedy zdecydujemy 9.

4  c 
2 6 a e 
1 3 5 7 b d f 

Następnie za.

4 c 
2 6 e 
1 3 5 7b d f 

Następnie b.

4 c 
2 6 e 
1 3 5 7 d f 

Następnie c.

4 
2 6 e 
1 3 5 7d f 

Et cetera.

Answer 4

Tak dodałem elementy do drzewa b-tree.

Dzięki Steve314, za danie mi start z reprezentacji binarnej

Podano n elementów do dodania, w kolejności. Musimy dodać go do m-porządku b-drzewa. Weź indeksy (1 ... n) i przekonwertuj je na wysokość m. Główną ideą tego wstawienia jest wstawienie numeru z najwyższym bitem m-radix obecnie i utrzymanie go powyżej numerów mniejszych m-radix dodanych w drzewie mimo podziału węzłów.

1,2,3 .. są indeksami, więc faktycznie wstawia się numery, na które wskazują.

For example, order-4 tree 
     4  8   12   highest radix bit numbers 
1,2,3 5,6,7 9,10,11 13,14,15 

Teraz w zależności od zlecenia mediany może być:

• zamówienie jest nawet -> liczba klawiszy są nieparzyste -> mediana jest środkowy (mid mediana)
• zamówienie jest nieparzysta - liczba> z klawisze są równe -> lewa mediana lub prawa mediana

Wybór median (lewo/prawo) do awansu będzie decydował o kolejności, w jakiej powinienem wstawiać elementy. To musi być naprawione dla b-drzewa.

Dodaję elementy do drzew w wiadrach. Najpierw dodaję elementy kubełkowe, a następnie uzupełniam kolejne wiadro. Wiadra można łatwo utworzyć, jeśli znana jest mediana, rozmiar wiadra to kolejność m.

I take left median for promotion. Choosing bucket for insertion. 
    | 4  | 8  | 12  |  
1,2,|3 5,6,|7 9,10,|11 13,14,|15 
     3  2   1    Order to insert buckets. 

• Na lewej mediana wybór wstawić do wiadra drzewie zaczynając od prawej strony do prawej środkowej wyboru wstawić wiadra z lewej strony. Wybierając lewy-środkowy, najpierw wstawiamy medianę, potem elementy na lewo od niej, a potem resztę liczb w wiadrze.

Przykład

Bucket median first 
12, 
Add elements to left 
11,12, 
Then after all elements inserted it looks like, 
| 12  | 
|11 13,14,| 
Then I choose the bucket left to it. And repeat the same process. 
Median 
    12   
8,11 13,14, 
Add elements to left first 
     12   
7,8,11 13,14, 
Adding rest 
    8  | 12   
7 9,10,|11 13,14, 
Similarly keep adding all the numbers, 
    4  | 8  | 12   
3 5,6,|7 9,10,|11 13,14, 
At the end add numbers left out from buckets. 
    | 4  | 8  | 12  | 
1,2,|3 5,6,|7 9,10,|11 13,14,|15 

• Do połowy mediany (nawet zamówić B-drzewach) wystarczy wstawić medianę, a następnie wszystkie numery w wiadrze.

• Dla prawej mediany dodaję łyżki od lewej. W przypadku elementów w pojemniku najpierw wstawiam elementy medianowe, potem prawe, a następnie lewe.

Tutaj dodajemy najwyższe numery m-pozycyjnego, aw procesie dodałem numery z natychmiastowym mniejszym kawałku m-radix, upewniając się, że największą liczbę m-Radix pobyt na szczycie. Tutaj mam tylko dwa poziomy, dla kolejnych poziomów powtarzam ten sam proces w malejącej kolejności bitów radix.

Ostatnim przypadkiem jest, gdy pozostałe elementy są tego samego radix-bit i nie ma liczb z mniejszym bitem radix, a następnie po prostu wstaw je i zakończ procedurę.

Podam przykład dla 3 poziomów, ale jest zbyt długi, aby pokazać. Więc spróbuj z innymi parametrami i powiedz, czy to działa.

Answer 5

Więc jest jakiś szczególny sposób określić kolejność wkładania co zmniejszyłoby zużycie przestrzeń?

Edit uwaga: ponieważ pytanie było dość ciekawe, staram się poprawić moją odpowiedź z odrobiną Haskell.

Let k być kolejność Knuth B-Tree i list listę kluczy

Minimalizacja zużycia przestrzeni ma trywialne rozwiązanie:

-- won't use point free notation to ease haskell newbies 
trivial k list = concat $ reverse $ chunksOf (k-1) $ sort list 

Taki algorytm skutecznie produkować czasowo nieefektywne B-Tree, niewyważone po lewej stronie, ale przy minimalnym zużyciu space.

Istnieje wiele nieistotnych rozwiązań, które są mniej wydajne w produkcji, ale mają lepszą wydajność wyszukiwania (niższa wysokość/głębokość). Jak wiesz, to wszystko o kompromisach!

prosty algorytm, który minimalizuje zarówno głębokość B-drzewo i zużycie przestrzeni (ale nie ma zminimalizować wydajność odnośnika!), Jest następujący

-- Sort the list in increasing order and call sortByBTreeSpaceConsumption 
-- with the result 
smart k list = sortByBTreeSpaceConsumption k $ sort list 

-- Sort list so that inserting in a B-Tree with Knuth order = k 
-- will produce a B-Tree with minimal space consumption minimal depth 
-- (but not best performance) 
sortByBTreeSpaceConsumption :: Ord a => Int -> [a] -> [a] 
sortByBTreeSpaceConsumption _ [] = [] 
sortByBTreeSpaceConsumption k list 
    | k - 1 >= numOfItems = list -- this will be a leaf 
    | otherwise = heads ++ tails ++ sortByBTreeSpaceConsumption k remainder 
    where requiredLayers = minNumberOfLayersToArrange k list 
      numOfItems = length list 
      capacityOfInnerLayers = capacityOfBTree k $ requiredLayers - 1 
      blockSize = capacityOfInnerLayers + 1 
      blocks = chunksOf blockSize balanced 
      heads = map last blocks 
      tails = concat $ map (sortByBTreeSpaceConsumption k . init) blocks 
      balanced = take (numOfItems - (mod numOfItems blockSize)) list 
      remainder = drop (numOfItems - (mod numOfItems blockSize)) list 

-- Capacity of a layer n in a B-Tree with Knuth order = k 
layerCapacity k 0 = k - 1 
layerCapacity k n = k * layerCapacity k (n - 1) 

-- Infinite list of capacities of layers in a B-Tree with Knuth order = k 
capacitiesOfLayers k = map (layerCapacity k) [0..] 

-- Capacity of a B-Tree with Knut order = k and l layers 
capacityOfBTree k l = sum $ take l $ capacitiesOfLayers k 

-- Infinite list of capacities of B-Trees with Knuth order = k 
-- as the number of layers increases 
capacitiesOfBTree k = map (capacityOfBTree k) [1..] 

-- compute the minimum number of layers in a B-Tree of Knuth order k 
-- required to store the items in list 
minNumberOfLayersToArrange k list = 1 + f k 
    where numOfItems = length list 
      f = length . takeWhile (< numOfItems) . capacitiesOfBTree 

Dzięki tej smart funkcji dali list = [21, 18, 16, 9, 12, 7, 6, 5, 1, 2] i B Drzewo z rzędu Knuth = 3 należy uzyskać [18, 5, 9, 1, 2, 6, 7, 12, 16, 21] z otrzymanego B drzewne jak

   [18, 21] 
      /
     [5 , 9] 
    / | \ 
[1,2] [6,7] [12, 16] 

Oczywiście nie jest optymalne z POIN wydajnością t widzenia, ale powinno być dopuszczalne, ponieważ uzyskanie lepszego (jak poniżej) byłoby znacznie droższe (obliczeniowo i ekonomicznie):

  [7 , 16] 
     / | \ 
    [5,6] [9,12] [18, 21] 
    /
[1,2] 

Jeśli chcesz, aby go uruchomić, skompilować powyższy kod w Main.hs pliku i skompilować go z GHC po poprzedzenie

import Data.List (sort) 
import Data.List.Split 
import System.Environment (getArgs) 

main = do 
    args <- getArgs 
    let knuthOrder = read $ head args 
    let keys = (map read $ tail args) :: [Int] 
    putStr "smart: " 
    putStrLn $ show $ smart knuthOrder keys 
    putStr "trivial: " 
    putStrLn $ show $ trivial knuthOrder keys