¿Cuáles son las ventajas de los árboles T sobre árboles B +/-?

Question

He explorado las definiciones de T-trees y árboles B-/B +. De los documentos en la web entiendo que los B-trees funcionan mejor en la memoria jerárquica, como las unidades de disco y la memoria en caché.

Lo que no puedo entender es por qué se usaron árboles T incluso para memoria plana?

Se anuncian como una alternativa de espacio eficiente a los árboles AVL.

En el peor de los casos, todos los nodos hoja de un árbol T contienen solo un elemento y todos los nodos internos contienen la cantidad mínima permitida, que es casi total. Esto significa que, en promedio, solo se utiliza la mitad del espacio asignado. A menos que esté equivocado, esta es la misma utilización que el peor de los árboles B, cuando los nodos de un árbol B están medio llenos.

Suponiendo que ambos árboles almacenen las claves localmente en los nodos, pero utilicen punteros para hacer referencia a los registros, la única diferencia es que B-trees tiene que almacenar punteros para cada una de las ramas. Esto generalmente causaría hasta un 50% de sobrecarga o menos (sobre árboles T), dependiendo del tamaño de las teclas. De hecho, esto está cerca de la sobrecarga esperada en los árboles AVL, suponiendo que no hay un puntero principal, registros incrustados en los nodos, claves incrustadas en los registros. ¿Es esta la ganancia de eficiencia esperada que nos impide usar B-trees en su lugar?

Los árboles T generalmente se implementan en la parte superior de los árboles AVL. Los árboles AVL son más equilibrados que los B-trees. ¿Se puede conectar esto con la aplicación de T-trees?

Answer 1

Puedo darte una historia personal que cubre la mitad de la respuesta, es decir, por qué escribí un código de Pascal para el programa B+ trees hace unos 18 años.

mi sistema de destino era una PC con dos unidades de disco, tenía que almacenar un índice en la memoria no volátil y quería entender mejor lo que estaba aprendiendo en la universidad. Estaba muy insatisfecho con el rendimiento de un paquete comercial, probablemente DBase III, o algún producto de Fox, no lo recuerdo.

de todos modos: I necesita estas operaciones:

• de búsqueda
• inserción
• eliminación
• siguiente elemento

• elemento anterior

• tamaño máximo de índice no era conocido

• lo que los datos tenían que residir en el disco
• cada acceso al soporte tenía alto costo
• la lectura de un bloque entero cuesta lo mismo que leer un byte

árboles B + hizo ese pequeño PC lenta realmente vuela a través de los datos!

las hojas tenían dos punteros adicionales por lo que formaron una lista doblemente vinculada, para búsquedas secuenciales.

Answer 2

En realidad, la diferencia radica en el sistema que utiliza. Como lo comentó mi tutor en la universidad: si su problema radica en la falta de memoria o en la escasez de discos duros, determinará qué árbol y en qué implementación usará. Lo más probable es que sea B + árbol.

Dado que hay cientos de implementaciones, por ejemplo con 2direction queue y una cola direccional donde se deben crear elementos de pensamiento, y también hay múltiples formas de almacenar el índice y recuperarlo, se determinarán los inconvenientes y minutos reales de cualquier implementación.