Utilizando dos bases de datos para ilustrar este ejemplo: CouchDB y Cassandra.

CouchDB usa un árbol B + para los índices de documentos (usando una modificación inteligente para trabajar en su entorno de solo agregar): más específicamente, a medida que los documentos se modifican (insertar / actualizar / eliminar), se añaden al archivo de base de datos en ejecución, así como a una hoja completa -> Ruta de nodo desde el árbol B + de todos los nodos efectuado por la revisión actualizada justo después del documento.

Estas revisiones de índice fragmentadas están alineadas junto con las modificaciones, de modo que el índice completo es una unión de las modificaciones de índice más recientes agregadas al final del archivo junto con piezas adicionales más atrás en el archivo de datos que aún son relevantes y refugiadas. aún no se ha modificado.

Buscando el B + árbolis O (logn).

Cassandra mantiene las claves de registro ordenadas, en memoria, en tablas (pensemos en ellas como matrices para esta pregunta) y las escribe como separadas (ordenadas) tablas de cadenas ordenadas de vez en cuando

Podemos pensar en la colección de todas estas tablas como el "índice" (por lo que entiendo).

Cassandra está obligada a compact / combine estas tablas de cadenas ordenadas de vez en cuando, creando una representación de archivo más completa del índice.

Buscandouna matriz ordenada es O (logn).

Suponiendo un nivel de complejidad similar entre mantener fragmentos parciales de árbol B + en CouchDB versus índices parciales de cadenas ordenadas en Cassandra y dado que ambos proporcionan un tiempo de búsqueda O (logn), ¿cuál cree que sería una mejor representación de un índice de base de datos y ¿por qué

Soy específicamente curioso si hay un detalle de implementación sobre uno sobre el otro que lo haceparticularment atractivo o si ambos son un lavado y usted simplemente elige la estructura de datos con la que prefiere trabajar / tiene más sentido para el desarrollador.

Gracias por los pensamientos.