¿Almacenar varias claves por nodo, como en B, B + Árboles, es un concepto válido?

Para responder a esta pregunta, haremos una serie de experimentos con las bases de datos AVL, que contienen solo un desplazamiento de datos en el nodo (es decir, ninguna clave). Nos limitaremos a los discos duros, teniendo en cuenta que los SSD son 100 veces más rápidos. Considere el siguiente programa.

// SetB – Bases de datos – Prueba de rendimiento de conjuntos.

utilizando el sistema;
utilizando IPlusPlus.Persist;

el espacio de nombres persiste
{
Programa de clase
{
vacío estático Main (string [] args)
{
Set sA = new Set (“SetA”);

Aleatorio aleatorio = nuevo Aleatorio ();

DateTime Start = DateTime.Now;

Transacciones largas = 0;

para (int i = 0; i <100; i ++)
{
int j = random.Next ()% 100;
Transacciones ++;
if (! sA [“String” + j.ToString ()])
{
Transacciones ++;
sA.Add (“Cadena” + j.ToString ());
}

j = random.Next ()% 100;
Transacciones ++;
if (sA [“Cadena” + j.ToString ()])
{
Transacciones ++;
sA.Remove (“String” + j.ToString ());
}
}

DateTime Finish = DateTime.Now;

double Minutes = (double) ((Finish – Start) .Minutes);
segundos dobles = (doble) ((Finalizar – Inicio). Segundos);
doble milisegundos = (doble) ((Finalizar – Inicio). Milisegundos);
tasa doble = 1000 * (doble) Transacciones / (60000 * Minutos + 1000 * Segundos + Milisegundos);

Console.WriteLine (“{0} transacciones en el tiempo {1}, {2} transacciones / segundo”, Transacciones, Finish – Start, (int) Rate);
Console.WriteLine (“Nombre: {0} Directorio: {1}”, sA.Name, sA.Directory);
Console.WriteLine (“Longitud: {0}”, sA.Count);
}
}
}

Este programa, que realiza búsquedas aleatorias, adiciones y eliminaciones, produce el siguiente resultado en un HDD.

301 transacciones a tiempo 00: 00: 10.5877809, 28 transacciones / segundo
Nombre: SetA Directorio: c: \ IPlusPlus \ Data
Longitud: 54

Tenga en cuenta que esto va de 28 transacciones / segundo a 1700 transacciones / segundo en la unidad de estado sólido.

Estas cifras aún no nos permiten responder la pregunta. Considere el siguiente programa, que realiza solo lecturas.

// SetC – Bases de datos – Prueba de rendimiento de conjuntos.
// Pruebas de solo lectura.

utilizando el sistema;
utilizando IPlusPlus.Persist;

el espacio de nombres persiste
{
Programa de clase
{
vacío estático Main (string [] args)
{
Set persistentSet = new Set (“PersistentSet”);

Aleatorio aleatorio = nuevo Aleatorio ();

DateTime Start = DateTime.Now;

Transacciones largas = 0;

para (int i = 0; i <100; i ++)
{
int j = random.Next ()% 100;
Transacciones ++;
if (! persistentSet [“String” + j.ToString ()])
{
// Transacciones ++;
// persistentSet.Add (“String” + j.ToString ());
}

j = random.Next ()% 100;
Transacciones ++;
if (persistentSet [“String” + j.ToString ()])
{
// Transacciones ++;
// persistentSet.Remove (“String” + j.ToString ());
}
}

DateTime Finish = DateTime.Now;

double Minutes = (double) ((Finish – Start) .Minutes);
segundos dobles = (doble) ((Finalizar – Inicio). Segundos);
doble milisegundos = (doble) ((Finalizar – Inicio). Milisegundos);
tasa doble = 1000 * (doble) Transacciones / (60000 * Minutos + 1000 * Segundos + Milisegundos);

Console.WriteLine (“{0} transacciones en el tiempo {1}, {2} transacciones / segundo”, Transacciones, Finish – Start, (int) Rate);
Console.WriteLine (“Nombre: {0} Directorio: {1}”, persistentSet.Name, persistentSet.Directory);
Console.WriteLine (“Longitud: {0}”, persistentSet.Count);
}
}
}

Este programa produce el siguiente resultado.

200 transacciones a tiempo 00: 00: 00.0309677, 6666 transacciones / segundo
Nombre: Directorio de conjunto persistente: c: \ IPlusPlus \ Data
Longitud: 42

Vemos que mientras las adiciones y eliminaciones continúan a 28 transacciones / segundo, las lecturas se ejecutan a casi 7000 transacciones / segundo. Esto se debe al almacenamiento en caché del sistema de archivos.

Entonces, ¿qué implicaciones tiene esto para el viejo árbol B y el árbol B +? La motivación principal detrás de múltiples claves por nodo es acelerar las lecturas. Pero podemos ver de lo anterior que las lecturas ya son muy rápidas: solo las actualizaciones son lentas. Esto pone en duda la motivación detrás del diseño de B Trees y B + Trees, que es la mayor parte de la teoría moderna de bases de datos.

Definitivamente es un concepto válido. Una aplicación típica de árboles B / B + es donde tiene que procesar más datos en cualquier momento de los que se pueden manejar solo con almacenamiento primario (RAM).

Los dispositivos de almacenamiento secundarios son mucho más lentos y propensos al desgaste, por lo que querrá minimizar el acceso a estos dispositivos. Los árboles B están diseñados con ese objetivo en mente.