c# - son - b-tree base de datos
B-Trees/B+Trees y llaves duplicadas (4)
Intentando responder a mi propia pregunta ... También me gustaría recibir otras respuestas.
Llaves duplicadas
El árbol almacenará una referencia a una lista (memoria) o lista vinculada (disco) de elementos con la clave dada, si hay una posibilidad de entradas duplicadas para la misma clave.
B + nodos de árbol, tipos de cambio
En memoria, mis nodos tienen una referencia de object , que puede apuntar a otro nodo (en sí mismo otro árbol B + válido) en el caso de un nodo interno / de rama, o incluso datos directamente en el caso de un nodo externo / hoja. En el disco, esto funcionaría de una manera muy similar: un valor de 64 bits para cada "ranura de enlace", ya que he elegido nombrarlos, ya sea un desplazamiento en el archivo si apunta a un subnodo, o un número de bloque si apunta directamente a los datos (o al encabezado de una lista vinculada en el caso mencionado en la primera parte de la pregunta).
Estoy investigando la posibilidad de armar un esquema de almacenamiento personalizado para mi aplicación. Merece la pena el esfuerzo de reinventar potencialmente la rueda, creo, porque tanto el rendimiento como la eficiencia del almacenamiento son un objetivo principal y los datos y las operaciones en él son mucho más simples que todo proporcionado por un RDBMS (sin actualizaciones, sin eliminaciones, conjunto predefinido de consultas )
Estoy utilizando solo un pequeño puñado de recursos web que he encontrado sobre árboles B y árboles B + - Wikipedia, http://www.bluerwhite.org/btree/ , http://slady.net/java/bt /view.php , http://www.brpreiss.com/books/opus6/html/page342.html (el último es el más valioso).
Llaves duplicadas
El primer problema que estoy tratando de resolver es cómo lidiar con claves duplicadas: este árbol actuará como un índice DB y, por ejemplo, no habrá una sola ''cosa'' con ''color = red'', así que buscaré '' rojo ''en este árbol debería arrojar muchos resultados.
Hay dos soluciones que he encontrado hasta ahora. El primero es simplemente tener múltiples entradas en el árbol para cada una de estas. Pero cuando hay 100,000 o 1,000,000 cosas ''rojas'' en el árbol ... ¿es eso muy eficiente para la estructura de un árbol? El segundo era tener solo una entrada para cada clave, pero la ''carga útil'' asociada con cada tecla apunta a un bloque de datos diferente, que es una lista vinculada que apunta a todas las instancias de elementos que son ''rojos''.
¿Hay una opción común / mejor?
B + nodos de árboles que cambian tipos
Quería verificar una suposición que estoy haciendo. Digamos que tiene un B + -Tree, altura 2 - los nodos externos (hoja) en el nivel 2 contienen ''datos reales''. Entonces, una inserción necesita una división de un nodo hoja: el nodo hoja ya no contiene "datos reales". ¿Tengo razón al pensar que en términos de implementación porque los datos pueden ser de un tamaño sustancial, en su lugar, se almacena una especie de "puntero" como los "datos reales", por lo que si un nodo hoja se convierte en un nodo de rama, ese puntero (de el mismo tamaño) se actualiza para apuntar al nuevo subárbol?
Con eso quiero decir, nodos internos y externos, deberían tener el mismo tamaño, ya que los nodos externos podrían convertirse en internos, y mezclar datos no es una buena idea.
(Se agregó la etiqueta C # porque estoy implementando esto desde cero en C #).
Kieren, estoy seguro de que descubrió que los árboles B + crecen dividiéndose hacia arriba, de modo que un nodo hoja siempre es un nodo hoja, y los nodos internos siempre son nodos internos. Eventualmente, debe dividir el nodo raíz, que lo convierte en dos partes internas, y usted define una nueva raíz. Entonces, para responder la segunda parte de su pregunta, no cambia los tipos de nodo.
Con respecto a la primera parte de su pregunta, cuando borre un registro de datos del DB, necesitará encontrar todas las claves que apuntan a ese registro en particular, y eliminarlas. Si tiene que mirar a través de largas listas lineales para hacer eso, eliminar será lento. Supongo que está utilizando una búsqueda binaria dentro de un nodo para encontrar rápidamente el elemento de nodo correcto (tecla + puntero), de modo que si hace que ese mecanismo de "búsqueda de nodos" incluya la capacidad de solicitar una combinación de tecla + puntero particular, puede encontrar rápidamente el elemento clave correcto para eliminar. En otras palabras, haga que el puntero del registro de datos sea parte de la búsqueda (solo cuando busque la clave de un registro de datos en particular). Esto significa que las claves duplicadas se almacenarán en los nodos en el orden "puntero de datos", por lo que siempre que el orden de las claves duplicadas no sea importante, este mecanismo funcionará.
Cuando maneja claves duplicadas, siempre golpea una hoja que contiene la clave dada que buscó.
Como una hoja agrupa todas las teclas juntas, solo necesita caminar la hoja hacia la izquierda (posición -1) para encontrar la primera entrada con la tecla dada. Si encuentra la primera clave de la hoja, debe inspeccionar las hojas anteriores.
Como no hay una posible suposición acerca de la hoja, presionará una tecla duplicada, debe recorrer todas las hojas anteriores hasta que encuentre una hoja cuya primera clave no es la clave que busca. Si la última clave de esa hoja no es la clave que busca (<), es la siguiente hoja, en caso contrario, esta hoja.
La búsqueda sobre las hojas es lineal dentro de la hoja que tiene log n para encontrar la primera entrada de clave.
Si puede ordenar las entradas clave en la hoja por los datos que contienen, puede encontrar fácilmente la hoja para encontrar una entrada determinada (que es ideal para contener y eliminar operaciones).
para una alta probabilidad de duplicados, es mejor buscar otro modelo de almacenamiento almacenando clave -> datas. Especialmente si los datos no cambian a menudo.
[Actualizar]
Existe la posibilidad de olvidar una clave:
Nodo N [L1 | 3 | L2] Hoja L1 [1,2,3] -> L2 [3, 4, 5]
Eliminas los 3 en L2 que resultas.
Nodo N [L1 | 3 | L2] Hoja L1 [1,2,3] -> L2 [4, 5]
Cuando buscas ahora encuentras que 3 no está en L2. Ahora puede buscar en la hoja anterior para encontrar el 3.
Otra forma es actualizar la clave a la primera clave real de la hoja, lo que da como resultado (lo que resulta en la posible propagación de la actualización):
Nodo N [L1 | 4 | L2] Hoja L1 [1,2,3] -> L2 [4, 5]
O tomas prestado de la hoja izquierda el elemento.
Nodo N [L1 | 3 | L2] Hoja L1 [1,2] -> L2 [3, 4, 5]
Tiendo a usar la primera solución ya que también funciona para hojas en el medio de duplicados de hojas múltiples.
La característica principal de los árboles B + es la minimización de las búsquedas en disco. Si solo "almacena punteros", vence ese beneficio y su código perseguirá punteros a los archivos, y buscará la cabeza del disco por todos lados. No puede leer un centenar de bytes del disco, todas las lecturas y escrituras están en bloques alineados.
Padres de hojas: los datos están siempre en una hoja, y solo una tecla por hoja está en los nodos (que son los padres inmediatos de las hojas). El nodo le permite "mirar" el contenido de la hoja al mirar una copia de la primera clave en esa hoja, allí mismo, en el nodo.
Padres del nodo: la clave antes de la primera clave en el nodo hijo está en el padre del nodo.
La duplicación de datos no está mal. Por ejemplo, si hay 207 registros por hoja y hay 268 registros por nodo, entonces almacenará una clave adicional por cada 207 registros. Si tiene más de 207 * 269 hojas, necesita una clave más por cada 207 * 269 registros.
Parece que estás confundiendo árboles B y árboles B +. Los árboles B + siempre tienen los datos en las hojas, y nunca hay datos en los nodos. Solo una muestra de la clave más baja por niño está presente en un nodo. Los datos nunca "ascienden" en un árbol B +, solo las copias de una clave más baja por niño se propagan hacia arriba.
La sobrecarga crece logarítmicamente. La duplicación mínima ahorra muchas búsquedas.
(Realmente) teclas duplicadas
Para manejar claves duplicadas en un árbol B +, como en varias filas que tienen el mismo valor, las implementaciones normalmente lo fuerzan a ser único al agregar una columna oculta adicional a la tabla y asignarle un valor de incremento automático cuando se crea un registro. La columna oculta se agrega al final de la clave indexada, lo que garantiza que siempre será única. El índice comienza con las columnas indexadas, por lo que el orden será el especificado, pero el valor oculto adjunto garantiza la exclusividad.
Si la tabla ya tiene una clave principal, podría usarla para aplicar exclusividad en lugar de agregar una columna oculta.