In che ordine si dovrebbe inserire un set di chiavi conosciute in un B-Tree per ottenere un'altezza minima?

Question

Dato un numero fisso di chiavi o valori (memorizzati nell'array o in una struttura di dati) e l'ordine di b-tree, è possibile determinare la sequenza di inserimento di chiavi che genererebbe un b-tree efficiente in termini di spazio.

Per illustrare, considerare l'albero b dell'ordine 3. Lasciare le chiavi {1,2,3,4,5,6,7}. Inserimento di elementi in albero nel seguente ordine

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

creerebbe un albero come questo

 4 
    2  6 
    1 3 5 7 

vedere http://en.wikipedia.org/wiki/B-tree

Ma l'inserimento di elementi in questo modo

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; 
    } 
} 

crea un albero così

3 5 
1 2 4 6 7 

dove possiamo vedere c'è diminuzione di livello.

Quindi esiste un modo particolare per determinare la sequenza di inserimento che ridurrebbe il consumo di spazio?

Answer 1

Sfortunatamente, tutti gli alberi presentano i peggiori tempi di esecuzione dello scenario e richiedono tecniche di bilanciamento rigide quando i dati vengono immessi in ordine crescente in questo modo. Gli alberi binari si trasformano rapidamente in liste concatenate, ecc.

Per i tipici casi di utilizzo B-tree (database, filesystem, ecc.), Si può in genere contare su dati più distribuiti, producendo un albero più simile al secondo esempio.

Anche se è davvero una preoccupazione, è possibile annullare ogni chiave, garantendo una più ampia distribuzione di valori.

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

Answer 2

il seguente trucco dovrebbe funzionare per gli alberi di ricerca più ordinate, assumendo i dati da inserire sono i numeri interi 1..n.

Si consideri la rappresentazione binaria delle vostre chiavi intere - per 1..7 (con i puntini di zeri) che è ...

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

Bit 2 cambi meno spesso, il bit 0 cambiamenti più spesso. Questo è l'opposto di ciò che vogliamo, quindi cosa succede se invertiamo l'ordine di questi bit, quindi ordinare le nostre chiavi in ​​ordine di questo valore del bit-rovesciata ...

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 

E 'più semplice per spiegare questo in termini di albero di ricerca binaria sbilanciato, in crescita aggiungendo foglie. Il primo elemento è un punto morto: è esattamente l'elemento che vogliamo per la radice. Quindi aggiungiamo le chiavi per il livello successivo. Infine, aggiungiamo il livello foglia. Ad ogni passo, l'albero è il più equilibrato possibile, quindi anche se si sta costruendo un albero bilanciato AVL o rosso-nero, la logica di riequilibrio non dovrebbe mai essere invocata.

[EDIT Mi sono appena reso conto che non è necessario ordinare i dati in base a quei valori bit invertiti per poter accedere alle chiavi in ​​tale ordine. Il trucco consiste nel notare che l'inversione di bit è la sua inversa. Oltre a mappare i tasti per le posizioni, mappa le posizioni sui tasti. Quindi se passi da 1 a ..n, puoi usare questo valore di inversione di bit per decidere quale elemento inserire successivamente - per il primo inserto usa il quarto elemento, per il secondo inserto usa il secondo elemento e così via. Una complicazione: devi arrotondare verso l'alto fino a uno meno di una potenza di due (7 è OK, ma usa 15 invece di 8) e devi limitare i valori dei bit invertiti. La ragione è che po 'di inversione può muoversi alcune posizioni dentro il campo out-of-bounds e viceversa.]

In realtà, per un albero rosso-nero verrà richiamato una certa logica riequilibrio, ma dovrebbe essere solo ri-colorando i nodi - non riorganizzandoli. Tuttavia, non ho ricontrollato, quindi non fare affidamento su questa affermazione.

Per un albero B, l'altezza dell'albero aumenta con l'aggiunta di una nuova radice. Dimostrare che questo funziona è, quindi, un po 'scomodo (e potrebbe richiedere una divisione del nodo più attenta di quanto normalmente richiesto da un albero B), ma l'idea di base è la stessa. Sebbene il riequilibrio si verifichi, si verifica in modo equilibrato a causa dell'ordine degli inserti.

Questo può essere generalizzato per qualsiasi serie di chiavi note in anticipo perché, una volta ordinate le chiavi, è possibile assegnare indici adatti in base a tale ordine.

---

ATTENZIONE - Questo non è un modo efficace per costruire un albero perfettamente bilanciato da noti dati già ordinati.

Se i dati sono già stati ordinati e si conosce la loro dimensione, è possibile creare un albero perfettamente bilanciato nel tempo O (n). Ecco alcuni pseudocode ...

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 

Fondamentalmente, questo decide la struttura dell'albero in base alle dimensioni e attraversa quella struttura, costruendo i nodi effettivi lungo la strada. Non dovrebbe essere troppo difficile adattarlo per B Trees.

Answer 3

Per creare un albero B particolare utilizzando Insert() come una scatola nera, lavorare all'indietro. Dato un albero B non vuoto, trova un nodo con più del numero minimo di bambini che sia il più vicino possibile alle foglie. Si considera che la radice abbia un minimo 0, quindi esiste sempre un nodo con il numero minimo di figli. Eliminare un valore da questo nodo per aggiungerlo all'elenco delle chiamate Insert(). Lavora verso le foglie, unendo sottostrutture.

Ad esempio, dato l'albero 2-3

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

scegliamo 8 e fare si fonde per ottenere il predecessore

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

Poi abbiamo scelto 9.

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

Poi un.

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

Quindi b.

4 c 
2 6 e 
1 3 5 7 d f 

Quindi c.

4 
2 6 e 
1 3 5 7d f 

Et cetera.

Answer 4

Ecco come aggiungerei elementi a b-tree.

Grazie a Steve314, per avermi dato l'avvio con la rappresentazione binaria,

Dato sono n elementi da aggiungere, in ordine. Dobbiamo aggiungerlo a m-order b-tree. Prendi i loro indici (1 ... n) e convertilo in radix m. L'idea principale di questo inserimento è di inserire il numero con il bit m-radix più alto al momento e tenerlo al di sopra dei numeri m-radix minori aggiunti nell'albero nonostante la divisione dei nodi.

1,2,3 .. sono indici in modo da inserire effettivamente i numeri a cui puntano.

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

Ora, a seconda dell'ordine mediana può essere:

• ordine è anche -> numero di chiavi sono strano -> mediana è di mezzo (metà mediana)
• ordine è strano -> numero di le chiavi sono pari -> mediana sinistra o mediana destra

La scelta della mediana (sinistra/destra) da promuovere deciderà l'ordine in cui inserire gli elementi. Questo deve essere corretto per l'albero b.

Aggiungo elementi agli alberi in secchi. Per prima cosa aggiungo gli elementi del secchio quindi al completamento del prossimo secchio in ordine. I secchi possono essere facilmente creati se si conosce la mediana, la dimensione del secchio è l'ordine 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. 

• Per la scelta a sinistra-mediana I inserire secchi per l'albero a partire dal lato destro, per la corretta scelta mediana inserisco secchi dal lato sinistro. Scegliendo la mediana a sinistra inseriamo prima la mediana, poi gli elementi a sinistra di essa prima il resto dei numeri nel secchio.

Esempio

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 

• per la metà di mediana (anche di ordine b-alberi) è sufficiente inserire la mediana e quindi tutti i numeri nel secchio.

• Per la mediana di destra aggiungo i secchi da sinistra. Per gli elementi all'interno del bucket, prima inserisco elementi mediani, quindi elementi a destra e quindi elementi a sinistra.

Qui stiamo aggiungendo il numero più alto m-radix, e nel processo ho aggiunto i numeri con immediato minore bit m-radix, assicurandosi che il numero più alto m-radix a restare in cima. Qui ho solo due livelli, per più livelli ripeto lo stesso processo in ordine discendente di bit radix.

L'ultimo caso si verifica quando gli elementi rimanenti sono dello stesso bit-radice e non vi sono numeri con un bit-radix inferiore, quindi è sufficiente inserirli e completare la procedura.

Vorrei fare un esempio per 3 livelli, ma è troppo lungo per mostrare. Quindi, per favore prova con altri parametri e dire se funziona.

Answer 5

Quindi c'è un modo particolare per determinare la sequenza di inserimento che ridurrebbe il consumo spazio?

Modifica nota: dal momento che la domanda è stata molto interessante, cerco di migliorare la mia risposta con un po 'di Haskell.

Sia k essere l'ordine Knuth del B-Tree e list un elenco di chiavi

La minimizzazione del consumo di spazio ha una soluzione banale:

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

Tale algoritmo efficiente produrre un tempo-inefficiente B-Tree, sbilanciato a sinistra ma con il minimo consumo di spazio .

Esistono molte soluzioni non banali che sono meno efficienti da produrre ma mostrano migliori prestazioni di ricerca (altezza/profondità inferiori). Come sapete, è tutto sui trade-off!

Un semplice algoritmo che minimizza sia la profondità B-albero e il consumo di spazio (ma non minimizza prestazioni di ricerca!), È il seguente

-- 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 

Con questa funzione smart dato un list = [21, 18, 16, 9, 12, 7, 6, 5, 1, 2] e una struttura B con ordine knuth = 3 dovremmo avere [18, 5, 9, 1, 2, 6, 7, 12, 16, 21] con un conseguente B-Tree come

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

Ovviamente questo non è ottimale da un poin prestazioni t di vista, ma dovrebbe essere accettabile, dal momento che l'ottenimento di una migliore (come la seguente) sarebbe molto più costoso (computazionalmente ed economicamente):

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

Se si desidera eseguire, compilare il codice precedente in un Main.hs di file e compilare con ghc dopo anteponendo

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