database - studio - ¿Cómo, dado un conjunto predeterminado de claves, reordenar las claves de modo que se use el número mínimo de nodos al insertar en un árbol B?

import tags from rslogix 5000 to factorytalk (5)

Aquí hay una forma que llevaría a una altura mínima en cualquier BST (incluido el árbol b):

ordenar matriz
Digamos que puedes tener la tecla m en el árbol b
Divida la matriz recursivamente en m + 1 partes iguales usando las teclas m en el padre.
construya el árbol secundario de n / (m + 1) claves ordenadas usando la recursión.

ejemplo: -

m = 2 array = [1 2 3 4 5 6 7 8 9 10] divide array into three parts :- root = [4,8] recursively solve :- child1 = [1 2 3] root1 = [2] left1 = [1] right1 = [3] similarly for all childs solve recursively.

Así que tengo un problema que estoy bastante seguro de que es solucionable, pero después de muchas, muchas horas de reflexión y discusión, solo se ha logrado un progreso parcial.

El tema es el siguiente. Estoy construyendo un BTree de, potencialmente, unos pocos millones de llaves. Cuando se busca en BTree, el disco se envía a la memoria a pedido y cada página en funcionamiento es relativamente costosa. Esto significa efectivamente que queremos tener que atravesar la menor cantidad de nodos posible (aunque después de que un nodo haya sido atravesado, el costo de atravesar ese nodo, hasta ese nodo es 0). Como resultado, no queremos desperdiciar espacio al tener muchos nodos que se acercan a la capacidad mínima. En teoría, esto debería ser evitable (dentro de la razón) ya que la estructura del árbol depende del orden en que se insertaron las claves.

Por lo tanto, la pregunta es cómo reordenar las claves de modo que, una vez que se haya construido el BTree, se utilice la menor cantidad de nodos. Aquí hay un ejemplo:

Me topé con esta pregunta ¿En qué orden debería insertar un conjunto de claves conocidas en un árbol B para obtener una altura mínima? que lamentablemente hace una pregunta ligeramente diferente. Las respuestas, tampoco parecen resolver mi problema. También vale la pena agregar que queremos las garantías matemáticas que provienen de no construir el árbol manualmente, y solo usar la opción de inserción. No queremos construir un árbol manualmente, cometer un error y luego encontrarlo ¡no se puede buscar!

También me he topado con 2 trabajos de investigación que están tan cerca de resolver mi pregunta, ¡pero no están del todo ahí! Optimización de tiempo y espacio en árboles B y árboles 2,3 óptimos (de donde tomé la imagen anterior de hecho), discuta y cuantifique las diferencias entre espacio óptimo y espacio libre, pero no vaya tan lejos como para describa cómo diseñar una orden de inserción hasta donde puedo ver.

Cualquier ayuda en esto sería grandemente apreciada grandemente.

Gracias

Los trabajos de investigación se pueden encontrar en:

http://www.uqac.ca/rebaine/8INF805/Automne2007/Sujets2007Automne/p174-rosenberg.pdf

http://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1143&context=hmc_fac_pub

EDITAR :: Terminé llenando un esqueleto btree construido como se describe en los documentos anteriores con el algoritmo FILLORDER. Como se mencionó anteriormente, esperaba evitar esto, ¡sin embargo terminé implementándolo antes de que se publicaran las 2 respuestas excelentes!

El algoritmo a continuación debe funcionar para B-Trees con un número mínimo de claves en node = d y maximum = 2 * d Supongo que se puede generalizar para 2 * d + 1 max claves si se conoce la forma de seleccionar la mediana.

El algoritmo a continuación está diseñado para minimizar el número de nodos, no solo la altura del árbol.

El método se basa en la idea de colocar claves en cualquier hoja no llena o si todas las hojas están llenas para colocar la clave debajo del nodo no lleno más bajo.

Más precisamente, el árbol generado por el algoritmo propuesto cumple con los siguientes requisitos: Tiene la mínima altura posible; No tiene más de dos nodos no completos en cada nivel. (Siempre son los dos nodos más correctos).

Como sabemos que la cantidad de nodos en cualquier nivel, excepto la raíz, es estrictamente igual a la suma del número de nodos y el número total de claves en el nivel superior, podemos probar que no existe una reorganización válida de nodos entre niveles que disminuya el número total de nodos. Por ejemplo, el aumento del número de claves insertadas por encima de cualquier nivel determinado llevará a un aumento de los nodos en ese nivel y, en consecuencia, al aumento del número total de nodos. Si bien cualquier intento de disminuir el número de claves por encima de cierto nivel dará lugar a una disminución del número de nodos en ese nivel y no podrá ajustar todas las claves en ese nivel sin aumentar la altura del árbol. También es obvio que la disposición de las teclas en cualquier nivel es una de las óptimas. Usando el razonamiento anterior también se puede construir una prueba más formal a través de la inducción matemática.

La idea es mantener una lista de contadores (el tamaño de la lista no es mayor que la altura del árbol) para rastrear cuántas claves se agregaron en cada nivel. Una vez que agreguen d claves a algún nivel, significa que el nodo se llenó a la mitad creado en ese nivel y si hay suficientes claves para completar otra mitad de este nodo, deberíamos omitir estas claves y agregar la raíz para un nivel más alto. De esta manera, la raíz se colocará exactamente entre la primera mitad del subárbol anterior y la primera mitad del próximo subárbol, causará división, cuando la raíz tendrá su lugar y dos mitades de subárboles se separarán. El lugar para las claves omitidas estará seguro mientras pasamos por claves más grandes y se puede llenar más tarde.

Aquí está casi el código de trabajo (pseudo), la matriz debe ordenarse:

PushArray(BTree bTree, int d, key[] Array) { List<int> counters = new List<int>{0}; //skip list will contain numbers of nodes to skip //after filling node of some order in half List<int> skip = new List<int>(); List<Pair<int,int>> skipList = List<Pair<int,int>>(); int i = -1; while(true) { int order = 0; while(counters[order] == d) order += 1; for(int j = order - 1; j >= 0; j--) counters[j] = 0; if (counters.Lenght <= order + 1) counters.Add(0); counters[order] += 1; if (skip.Count <= order) skip.Add(i + 2); if (order > 0) skipList.Add({i,order}); //list of skipped parts that will be needed later i += skip[order]; if (i > N) break; bTree.Push(Array[i]); } //now we need to add all skipped keys in correct order foreach(Pair<int,int> p in skipList) { for(int i = p.2; i > 0; i--) PushArray(bTree, d, Array.SubArray(p.1 + skip[i - 1], skip[i] -1)) } }

Ejemplo:

Aquí es cómo deben ordenarse los números y las correspondientes teclas de los contadores para d = 2 mientras se pasa la matriz por primera vez. Marqué las teclas que presionaron en el árbol B durante la primera pasada (antes del bucle con recursión) con ''o'' y salté con ''x''.

24 4 9 14 19 29 0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18 20 21 22 23 25 26 27 28 30 ... o o x x o o o x x o o o x x x x x x x x x x x x o o o x x o o ... 1 2 0 1 2 0 1 2 0 1 2 0 1 ... 0 0 1 1 1 2 2 2 0 0 0 1 1 ... 0 0 0 0 0 0 0 0 1 1 1 1 1 ... skip[0] = 1 skip[1] = 3 skip[2] = 13

Debido a que no repasamos las claves omitidas, tenemos una complejidad de tiempo O (n) sin agregarlo al B-Tree y para la matriz ordenada;

En este formulario puede no estar claro cómo funciona cuando no hay suficientes claves para completar la segunda mitad del nodo después del bloque omitido, pero también podemos evitar saltear todas las teclas de omisión [orden] si la longitud total de la matriz es menor que ~ i + 2 * skip [order] y skip for skip [order - 1] en su lugar, tal cadena después de cambiar los contadores pero antes de cambiar la variable i podría agregarse:

while(order > 0 && i + 2*skip[order] > N) --order;

será correcto porque si el recuento total de claves en el nivel actual es menor o igual a 3 * d, aún se dividen correctamente si se agregan en el orden original. Esto conducirá a una reorganización ligeramente diferente de las claves entre los dos últimos nodos en algunos niveles, pero no romperá los requisitos descritos, y puede hacer que el comportamiento sea más fácil de entender.

Puede ser razonable encontrar alguna animación y ver cómo funciona, aquí está la secuencia que debe generarse en el rango 0..29: 0 1 4 5 6 9 10 11 24 25 26 29 / final de la primera pasada / 2 3 7 8 14 15 16 19 20 21 12 13 17 18 22 23 27 28

El algoritmo a continuación intenta preparar el orden de las claves para que no necesite tener poder ni conocimiento sobre el procedimiento de inserción. El único supuesto es que los nodos de árbol sobrellenados se dividen en la mitad o en la posición del último elemento insertado, de lo contrario, el árbol B se puede tratar como una caja negra.

El truco es desencadenar divisiones de nodo de forma controlada. Primero llene un nodo exactamente, la mitad izquierda con las teclas que pertenecen juntas y la mitad derecha con otro rango de teclas que pertenecen juntas. Finalmente, inserta una clave que se encuentra entre esos dos rangos pero que no pertenece a ninguno; los dos subrangos se dividen en nodos separados y la última clave insertada termina en el nodo principal. Después de dividirse de esta manera, puede llenar el resto de los dos nodos secundarios para que el árbol sea lo más compacto posible. Esto también funciona para los nodos principales con más de dos nodos secundarios, simplemente repita el truco con uno de los secundarios hasta que se cree el número deseado de nodos secundarios. A continuación, uso lo que conceptualmente es el nodo infantil más a la derecha como el "terreno de división" (pasos 5 y 6.1).

Aplique el truco de división de forma recursiva, y todos los elementos deben terminar en su lugar ideal (que depende del número de elementos). Creo que el siguiente algoritmo garantiza que la altura del árbol es siempre mínima y que todos los nodos, excepto la raíz, están lo más completos posible. Sin embargo, como probablemente pueda imaginar, es difícil estar completamente seguro sin implementarlo y probarlo a fondo. He intentado esto en papel y me siento confiado de que este algoritmo, o algo extremadamente similar, debería hacer el trabajo.

Árbol implícito T con factor de ramificación máximo M.

Procedimiento superior con teclas de longitud N :

Ordenar las llaves .
Establezca la altura mínima de árbol en ceil (log ( N +1) / log ( M )).
Llame a insert-chunk con chunk = keys y H = minimal-tree-height .

Procedimiento insert-chunk con trozo de longitud L , altura de subárbol H :

Si H es igual a 1:
1. Insertar todas las claves del trozo en T
2. Vuelve inmediatamente.
Ajuste el tamaño de subchunk ideal S a pow ( M , H - 1).
Establezca el número de subárboles T a ceil (( L + 1) / S ).
Establezca el tamaño de subchunk real S '' en ceil (( L + 1) / T ).
Recursivamente, llame a insert-chunk con chunk '' = las teclas del último piso (( S - 1) / 2) de chunk y H'' = H - 1.
Para cada uno de los subchunks ceil ( L / S '' ) (de tamaño S'' ) excepto el último con el índice I :
1. Recursivamente llame a insert-chunk con trozo '' = las primeras teclas ceil (( S - 1) / 2) del subchunk I y H'' = H - 1.
2. Inserte la última clave del subchunk I en T (esta inserción activa a propósito una división).
3. Recursivamente, llame a insert-chunk con trozo '' = las claves restantes del subchunk I (si existe) y H'' = H - 1.
Recursivamente, llame a insert-chunk with chunk '' = las teclas restantes del último subchunk y H'' = H - 1.

Tenga en cuenta que el procedimiento recursivo se llama dos veces para cada subárbol; eso está bien, porque la primera llamada siempre crea un medio subárbol perfectamente llenado.

Entonces, ¿se trata de optimizar el procedimiento de creación, u optimizar el árbol?

Puede crear claramente un árbol B de máxima eficiencia creando primero un árbol binario equilibrado completo y luego contrayendo nodos.

En cualquier nivel en un árbol binario, la brecha en los números entre dos nodos contiene todos los números entre esos dos valores por la definición de un árbol binario, y esta es más o menos la definición de un árbol-B. Simplemente comienza a contraer las divisiones del árbol binario en nodos B-Tree. Dado que el árbol binario está equilibrado por la construcción, los espacios entre nodos en el mismo nivel siempre contienen el mismo número de nodos (suponiendo que el árbol esté lleno). Así, el BTree así construido se garantiza equilibrado.

En la práctica, esta es probablemente una forma bastante lenta de crear un BTree, pero ciertamente cumple con sus criterios para construir el B-Tree óptimo, y la literatura sobre la creación de árboles binarios equilibrados es exhaustiva.

=====================================

En su caso, donde podría sacar un estante "mejor" de una versión óptima construida, ¿ha considerado simplemente cambiar la cantidad de nodos secundarios que puede tener? Su diagrama parece un árbol clásico 2-3, pero es perfectamente posible tener un árbol 3-4 o un árbol 3-5, lo que significa que cada nodo tendrá al menos tres hijos.

Su pregunta es sobre la optimización de btree. Es poco probable que hagas esto solo por diversión. Así que solo puedo asumir que le gustaría optimizar los accesos a los datos, tal vez como parte de la programación de la base de datos o algo así. Usted escribió: "Cuando se busca en BTree, el disco se envía a la memoria a pedido", lo que significa que no tiene suficiente memoria para realizar ningún tipo de almacenamiento en caché o tiene una política para utilizar la menor cantidad de memoria posible. De cualquier manera, esta puede ser la causa principal por la cual cualquier respuesta a su pregunta no será satisfactoria. Déjame explicarte por qué.

Cuando se trata de la optimización de acceso a datos, la memoria es tu amiga. No importa si la optimización de lectura o escritura necesita memoria. Cualquier tipo de optimización de escritura siempre funciona bajo el supuesto de que puede leer la información de manera rápida (desde la memoria); la clasificación necesita datos. Si no tiene suficiente memoria para la optimización de lectura, tampoco la tendrá para la optimización de escritura.

Tan pronto como esté dispuesto a aceptar al menos algo de uso de la memoria, puede replantearse su declaración "Al buscar en el BTree, se lo busca en la memoria desde el disco", lo que deja espacio para el equilibrio entre la optimización de lectura y escritura. Un máximo optimizado de BTREE es la optimización de escritura maximizada. En la mayoría de los escenarios de acceso a datos, sé que obtiene una escritura en cualquiera de las 10 a 100 lecturas. Eso significa que es probable que una optimización de escritura maximizada proporcione un rendimiento pobre en términos de optimización de acceso a datos. Es por eso que las bases de datos aceptan ciclos de reestructuración, pérdida de espacio clave, btrees desequilibrados y cosas por el estilo ...