algorithm - introduccion - ¿En qué orden debe insertar un conjunto de claves conocidas en un B-Tree para obtener una altura mínima?

introduccion de arboles by b+

Question

Dado un número fijo de claves o valores (almacenados en una matriz o en alguna estructura de datos) y el orden de b-tree, podemos determinar la secuencia de claves de inserción que generarían un b-tree eficiente en el espacio.

Para ilustrar, considere b-tree de orden 3. Deje que las claves sean {1,2,3,4,5,6,7}. Insertar elementos en el árbol en el siguiente orden

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

crearía un árbol como este

        4
     2      6
   1  3   5   7

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

Pero insertando elementos de esta manera

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 árbol como este

    3 5
1 2  4  6 7

donde podemos ver que hay una disminución en el nivel.

Entonces, ¿hay una forma particular de determinar la secuencia de inserción que reduciría el consumo de espacio?

Answer 1

Entonces, ¿hay una forma particular de determinar la secuencia de inserción que reduciría el consumo de espacio ?

Nota de edición : dado que la pregunta era bastante interesante, trato de mejorar mi respuesta con un poco de Haskell.

Deje k sea ​​el orden Knuth del árbol B y list una lista de claves

La minimización del consumo de espacio tiene una solución trivial:

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

Tal algoritmo producirá eficientemente un B-Tree ineficiente en tiempo , desequilibrado a la izquierda pero con un consumo de espacio mínimo.

Existen muchas soluciones no triviales que son menos eficientes de producir pero muestran un mejor rendimiento de búsqueda (menor altura / profundidad). Como sabes, ¡ todo se trata de intercambios !

Un algoritmo simple que minimiza tanto la profundidad del árbol B como el consumo de espacio (¡pero no minimiza el rendimiento de búsqueda!) Es el siguiente

-- 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 esta función smart dada una list = [21, 18, 16, 9, 12, 7, 6, 5, 1, 2] y un árbol B con knuth order = 3 debemos obtener [18, 5, 9, 1, 2, 6, 7, 12, 16, 21] con un B-Tree resultante como

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

Obviamente, esto no es óptimo desde el punto de vista del rendimiento, pero debería ser aceptable, ya que obtener uno mejor (como el siguiente) sería mucho más caro (computacional y económicamente):

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

Si desea ejecutarlo, compile el código anterior en un archivo Main.hs y compílelo con ghc después de anteponer

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

Answer 2

Así es como agregaría elementos a b-tree.

Gracias a Steve314, por darme el comienzo con la representación binaria,

Se dan n elementos para agregar, en orden. Tenemos que agregarlo a m-order b-tree. Toma sus índices (1 ... n) y conviértelos en radix m. La idea principal de esta inserción es insertar el número con el bit de m-radix más alto actualmente y mantenerlo por encima de los números de m-radix menores agregados en el árbol a pesar de la división de nodos.

1,2,3 .. son índices así que realmente insertas los números a los que apuntan.

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

Ahora, dependiendo de la mediana de la orden, puede ser:

• el orden es par -> el número de claves es impar -> la mediana es el medio (mediana mediana)
• el orden es impar -> el número de claves es par -> mediana izquierda o mediana derecha

La elección de la mediana (izquierda / derecha) que se promoverá decidirá el orden en el que debo insertar elementos. Esto tiene que ser arreglado para el b-tree.

Agrego elementos a los árboles en cubos. Primero agrego los elementos del cubo y luego al completar el siguiente cubo en orden. Los cubos se pueden crear fácilmente si se conoce la mediana, el tamaño del cubo es el orden 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.

• Para la opción de la mediana izquierda, inserto cubos en el árbol comenzando desde el lado derecho, para la opción de la mediana derecha, inserto cubos del lado izquierdo. Al elegir la mediana izquierda, insertamos la mediana primero, luego los elementos a la izquierda primero y luego el resto de los números en la cubeta.

Ejemplo

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 

• Para mid-median (incluso para b-trees) simplemente inserta la mediana y luego todos los números en el cubo.

• Para la mediana derecha, agrego cubos de la izquierda. Para los elementos dentro del cubo, primero inserto la mediana, luego los elementos a la derecha y luego los elementos a la izquierda.

Aquí estamos agregando los números más altos de m-radix, y en el proceso agregué números con bit de m-radix menor inmediato, asegurándome de que los números más altos de m-radix permanezcan en la parte superior. Aquí tengo solo dos niveles, para más niveles repito el mismo proceso en orden descendente de radix bits.

El último caso es cuando los elementos restantes son de la misma raíz-bit y no hay números con menos radix-bit, simplemente insértelos y termine el procedimiento.

Daría un ejemplo para 3 niveles, pero es demasiado largo para mostrar. Intente con otros parámetros y diga si funciona.

Answer 3

Desafortunadamente, todos los árboles exhiben los tiempos de ejecución de escenarios más desfavorables y requieren técnicas de equilibrio rígidas cuando los datos se ingresan en orden creciente de esa manera. Los árboles binarios se convierten rápidamente en listas vinculadas, etc.

Para casos típicos de uso de B-Tree (bases de datos, sistemas de archivos, etc.), normalmente puede contar con que sus datos estén distribuidos de forma más natural, produciendo un árbol más parecido al segundo ejemplo.

Sin embargo, si realmente es una preocupación, podría hash cada clave, garantizando una distribución más amplia de valores.

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

Answer 4

El siguiente truco debería funcionar para la mayoría de los árboles de búsqueda ordenados, suponiendo que los datos a insertar son los enteros 1..n .

Considere la representación binaria de sus claves enteras, para 1..7 (con puntos para ceros) que es ...

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

El bit 2 cambia con menos frecuencia, el bit 0 cambia con mayor frecuencia. Eso es lo opuesto a lo que queremos, entonces, ¿qué pasa si invertimos el orden de esos bits, luego ordenamos nuestras claves en orden de este valor invertido en bits ...

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

Es más fácil explicar esto en términos de un árbol de búsqueda binaria desequilibrado, creciendo al agregar hojas. El primer elemento está en el centro, es exactamente el elemento que queremos para la raíz. Luego agregamos las claves para la siguiente capa hacia abajo. Finalmente, agregamos la capa de la hoja. En cada paso, el árbol está tan equilibrado como puede, por lo que incluso si está construyendo un árbol equilibrado AVL o rojo-negro, la lógica de reequilibrio nunca debería invocarse.

[ EDITAR] Me acabo de dar cuenta de que no necesita ordenar los datos en función de esos valores invertidos en bits para acceder a las claves en ese orden. El truco para eso es darse cuenta de que la inversión de bit es su propia inversa. Además de asignar claves a las posiciones, asigna las posiciones a las claves. Por lo tanto, si recorre desde 1..n, puede usar este valor invertido en bits para decidir qué elemento insertar a continuación: para la primera inserción, utilice el 4º elemento, para la segunda inserción, utilice el segundo elemento, etc. Una complicación: tiene que redondear n hacia arriba a una potencia menor que dos (7 está bien, pero use 15 en lugar de 8) y tiene que comprobar los límites de los valores de bit invertido. La razón es que el cambio de bit puede mover algunas posiciones dentro de límites fuera de límites y viceversa.]

En realidad, para un árbol rojo-negro se invocará una lógica de reequilibrio, pero debería estar simplemente volviendo a colorear los nodos, no reorganizándolos. Sin embargo, no lo he comprobado dos veces, así que no confíe en este reclamo.

Para un árbol B, la altura del árbol crece agregando una nueva raíz. Demostrar que esto funciona es, por lo tanto, un poco incómodo (y puede requerir una división de nodos más cuidadosa que la que normalmente requiere un árbol B) pero la idea básica es la misma. Aunque se produce el reequilibrio, se produce de forma equilibrada debido al orden de las inserciones.

Esto se puede generalizar para cualquier conjunto de claves de avance anticipado porque, una vez que las claves se ordenan, puede asignar índices adecuados en función de ese orden ordenado.

ADVERTENCIA : esta no es una forma eficiente de construir un árbol perfectamente equilibrado a partir de datos conocidos ya clasificados.

Si ya tiene ordenados sus datos y conoce su tamaño, puede construir un árbol perfectamente equilibrado en el tiempo O (n). Aquí hay un pseudocódigo ...

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

Básicamente, esto decide la estructura del árbol en función del tamaño y atraviesa esa estructura, construyendo los nodos reales a lo largo del camino. No debería ser demasiado difícil adaptarlo para B Trees.

Answer 5

Para construir un árbol B particular utilizando Insertar () como una caja negra, trabaje hacia atrás. Dado un árbol B no vacío, busca un nodo con más de la cantidad mínima de hijos que esté lo más cerca posible de las hojas. Se considera que la raíz tiene un mínimo de 0, por lo que siempre existe un nodo con el número mínimo de hijos. Elimine un valor de este nodo que se agregará previamente a la lista de llamadas Insert (). Trabaja hacia las hojas, fusionando subárboles.

Por ejemplo, dado el árbol 2-3

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

elegimos 8 y hacemos fusiones para obtener el predecesor

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

Entonces elegimos 9.

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

Entonces un.

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

Entonces b.

   4   c
 2   6   e
1 3 5 7 d f

Entonces c.

   4
 2   6  e
1 3 5 7d f

Etcétera.