¿Es un índice no similar a un diccionario? Si tiene la llave, puede acceder de inmediato?¿Por qué la búsqueda de un índice tiene una complejidad logarítmica?
Al parecer, los índices se almacenan a veces como los árboles B ... ¿Por qué?
Los diccionarios no se ordenan de forma implícita, B-Tree s son.
Un índice B-Tree se puede utilizar para el acceso a distancia, así:
WHERE col1 BETWEEN value1 AND value2
o pedidos, así:
ORDER BY col1
Usted no puede acceder inmediatamente a una página en un índice de B-Tree: se necesita para recorrer las páginas secundarias cuyo número aumenta logarítmicamente.
Algunas bases de datos también admiten índices de tipo diccionario, a saber, HASH índices, en cuyo caso el tiempo de búsqueda es constante. Pero tales índices no se pueden usar para acceso u orden a distancia.
Los índices de la base de datos generalmente se almacenan (casi siempre) como B-Trees. Y todas las estructuras de árbol balanceadas tienen complejidad O (log n) para buscar.
'Diccionario' es un 'Resumen Tipo de datos' (ADT), es decir, es una descripción funcional que no designa una implementación. Algunos diccionarios podrían usar un Hashtable para la búsqueda O (1), otros podrían usar un árbol y lograr O (log n).
La razón principal de una base de datos utiliza B-trees (sobre cualquier otro tipo de árbol) es que los árboles B son auto-equilibrio y son muy 'superficial' (que requieren poca disco I/O)
Todos los árboles equilibrados lo hacen. Un árbol suficientemente degenerado es una lista vinculada. – Vatine
@Vatine: Tienes razón, lo editaré. –
uno de los únicos Las estructuras de datos a las que puede acceder de inmediato con una clave son un vector, que para una gran cantidad de datos, se vuelve ineficiente cuando comienza a insertar y eliminar elementos. También necesita una asignación de memoria contigua.
Un hash puede ser eficiente pero necesita más espacio y va a terminar con las colisiones.
A B árbol tiene un buen equilibrio entre el rendimiento y el espacio de búsqueda.
HashIndex (por ejemplo. En MySQL y postgres) tiene complejidad constante (O (1)) para la búsqueda.
CREATE INDEX ... USING HASH
¿no tendría complejidad de tiempo constante? Lineal es lo peor posible, es decir, buscar sin un índice. –
@ Il-Bhima, oh ... sí :) esto era un tipo de error mental. – osgx
Si sus consultas sólo son tests de igualdad a continuación, es verdad, los diccionarios son una buena elección, ya que van a hacer búsquedas en O amortizado (1) vez. Sin embargo, si desea extender las consultas para involucrar verificaciones de rango, por ejemplo (select * from students where age > 10), repentinamente sus diccionarios pierden completamente su ventaja. Aquí es donde entran los índices basados en árboles. Con un índice basado en árbol puede realizar igualdades y verificaciones de rango en tiempo logarítmico.
Hay un problema con las estructuras de árbol ingenuo. Se desequilibran, esto significa que después de agregar ciertos valores al índice, la estructura del árbol se desequilibra (por ejemplo, una línea larga) y las búsquedas comienzan a tomar O (N) de nuevo. Esto puede resolverse equilibrando tu árbol. El B-Tree es uno de esos enfoques que también aprovecha los sistemas capaces de hacer grandes bloques de E/S, por lo que es más apropiado para las bases de datos.
Puede lograr O(1) si preasignar N entradas de una matriz y de hash La clave de este N valores.
Pero luego, si tiene más de N entradas almacenadas, hay colisión. Por lo tanto, para cada clave del conjunto, tiene una lista de valor. Entonces ya no es exactamente O(1). El escaneo de la lista en sí será O(m) donde m es el número promedio de colisión.
Example with hash = n mod 3
0 --> [0,a] [3,b] ...
1 --> [1,a] [4,b] [7,b] ...
2 --> [2,a] [5,b] ...
En un punto en el tiempo, se convierte en algo de malo que se pasa más tiempo recorriendo la lista de valor de una clave potencial de utilizar otra estructura con O(log n) tiempo de búsqueda, donde n es el número total de entradas.
Por supuesto, puede elegir N tan grande que el array/hash sería más rápido que el B-Tree. Pero la matriz tiene un tamaño fijo preasignado. Entonces, si N = 1000 y almacena 3 valores, habrá desperdiciado 997 espacios en la matriz.
Así que es esencialmente un espacio de rendimiento trade-off. Para un pequeño conjunto de valores, array y hash es excelente. Para un gran conjunto de valores, B-Tree son los más eficientes.
hashes son los más rápidos buscar estructuras de datos, pero tienen algunos problemas:
a) no han sido clasificadas b) no importa lo bueno que el hash es, tendrá colisiones, que se convierte en un problema cuando una gran cantidad de datos c) encontrar un valor hash en un archivo indexado hash lleva mucho tiempo, por lo que la mayoría de las veces solo tiene sentido para los datos en memoria (RAM) que no son adecuados para las bases de datos, que la mayoría de las veces no caben todos datos en RAM
Los árboles ordenados abordan estos problemas, y las operaciones de b-trees en particular se pueden implementar de manera eficiente utilizando archivos. El único inconveniente es que tienen tiempos de búsqueda más lentos como una estructura hash.
Ninguna estructura de datos es perfecta en todos los casos, dependiendo del tamaño estimado de los datos y cómo se usa, uno es mejor.
Se pudo ordenar un diccionario. Simplemente no tiene que ser así. –
@Henk: corregido para aclarar esto. – Quassnoi
@Henk: Creo que los diccionarios se refieren a las tablas hash con acceso O (1). Se puede ordenar un diccionario, pero para hacer esa ordenación, tendrá una estructura lineal (es decir, consultas O (N)) o una estructura de árbol (O (logN)) debajo. –