Los sistemas de gestión de bases de datos proporcionan varios tipos de índices para mejorar el rendimiento y la integridad de los datos en diversas aplicaciones. Los tipos de índices incluyen árboles b , mapas de bits y árboles r .
En los sistemas de gestión de bases de datos, una estrategia de índice de clave inversa invierte el valor de la clave antes de introducirlo en el índice . [1] Por ejemplo, el valor 24538 se convierte en 83542 en el índice. Invertir el valor de la clave es particularmente útil para indexar datos como números de secuencia , donde cada nuevo valor de clave es mayor que el valor anterior, es decir, los valores aumentan de forma monótona. Los índices de clave inversa se han vuelto particularmente importantes en los sistemas de procesamiento de transacciones de alto volumen porque reducen la contención de los bloques de índice .
Los índices de clave invertida utilizan estructuras de árbol b , pero preprocesan los valores de clave antes de insertarlos. Simplificando, los árboles b colocan valores similares en un solo bloque de índice, por ejemplo, almacenando 24538 en el mismo bloque que 24539. Esto los hace eficientes tanto para buscar un valor específico como para encontrar valores dentro de un rango. Sin embargo, si la aplicación inserta valores en secuencia, cada inserción debe tener acceso al bloque más nuevo en el índice para agregar el nuevo valor. Si muchos usuarios intentan insertar al mismo tiempo, todos deben escribir en ese bloque y tienen que ponerse en línea, lo que ralentiza la aplicación. Esto es particularmente un problema en bases de datos agrupadas , que pueden requerir que el bloque se copie de la memoria de una computadora a la de otra para permitir que el próximo usuario realice su inserción.
Al invertir la clave, se distribuyen nuevos valores similares por todo el índice en lugar de concentrarlos en un único bloque de hojas. Esto significa que 24538 aparece en el mismo bloque que 14538, mientras que 24539 va a un bloque diferente, lo que elimina esta causa de contención . (Dado que 14538 se habría creado mucho antes que 24538, sus inserciones no interfieren entre sí).
Los índices inversos son tan eficientes como los índices no invertidos para encontrar valores específicos, aunque no son útiles para consultas de rango. Las consultas de rango son poco comunes para valores artificiales como números de secuencia. Al buscar el índice, el procesador de consultas simplemente invierte el objetivo de búsqueda antes de buscarlo.
Por lo general, las aplicaciones eliminan los datos más antiguos en promedio antes de eliminar los datos más nuevos. Por lo tanto, los datos con números de secuencia más bajos generalmente van antes que aquellos con valores más altos. A medida que pasa el tiempo, en los árboles b estándar , los bloques de índice para valores más bajos terminan conteniendo pocos valores, con un aumento proporcional en el espacio no utilizado, conocido como "rot". La podredumbre no solo desperdicia espacio, sino que también reduce la velocidad de las consultas, porque una fracción más pequeña de los bloques de un índice podrido cabe en la memoria en un momento dado. En un árbol b, si se elimina 14538, su espacio de índice permanece vacío. En un índice inverso, si 14538 va antes de que llegue 24538, 24538 puede reutilizar el espacio de 14538. [ cita requerida ]