¿Algún ejemplo de aplicaciones de producción que usan árboles de firmas?

Question

he estado leyendo mucho últimamente sobre los árboles de la firma, o S-árboles. Por ejemplo, this paper. La literatura habla muy bien de ellos, y se proporciona evidencia de mejoras de rendimiento considerables con respecto a, por ejemplo, los archivos invertidos o los árboles B, para algunas aplicaciones.

Ahora bien, ¿cómo es que no veo S-árboles utiliza mucho? ¿Conoces alguna instancia destacada de dicha estructura de datos en una aplicación popular? ¿Hay implementaciones DBMS que ofrecen índices de árbol de firmas?

Answer 1

He oído hablar de algo similar descrito como un "árbol en C": era parte de una base de datos de objetos y me imaginé que sus métodos de indexación eran similares a los que el documento describía en el enlace. Una empresa llamada InterSystems hace que un sistema de base de datos denominado caché que ellos describen como "post-relacional" y es muy jerárquica ... No sé lo suficiente sobre los detalles de estos diferentes sistemas para asegurarse de que todos son diferentes nombres para la misma funcionalidad, pero tienen algunos conceptos fundamentales superpuestos.

Answer 2

Ahora, ¿por qué es que no veo S-Trees usado mucho?

Incluir un nuevo método de indexación o unión en una base de datos es una tarea muy compleja.

MySQL, por ejemplo, aún no impone MERGE JOIN y que fueron inventados por, como, antiguos romanos o Arquímedes o por esa época.

Y el papel al que hace referencia es de fecha 2006 y este método ni siquiera se menciona en Wikipedia.

Esto significa que es aún desconocido, ya sea a los desarrolladores o no vale la pena usarlo en un RDBMS (o ambos).