¿Por qué la adición de un índice a un campo de base de datos acelera la búsqueda en ese campo?

Question

Soy nuevo en las bases de datos y he estado leyendo que agregar un índice a un campo que necesita buscar puede acelerar drásticamente los tiempos de búsqueda. Entiendo esta realidad, pero tengo curiosidad sobre cómo funciona realmente. He buscado un poco sobre el tema, pero no he encontrado ninguna respuesta buena, concisa y no demasiado técnica sobre cómo funciona.

He leído la analogía de que es como un índice en la parte posterior de un libro, pero en el caso de un campo de datos de elementos únicos (como direcciones de correo electrónico en una base de datos de usuario), usando la parte posterior de la analogía del libro proporcionaría el mismo tiempo de búsqueda lineal que una búsqueda no indexada.

¿Qué está pasando aquí para acelerar tanto los tiempos de búsqueda? He leído un poco acerca de buscar usando B+-Trees, pero las descripciones son un poco demasiado profundas. Lo que estoy buscando es una descripción general de alto nivel de lo que está sucediendo, algo que ayude a mi comprensión conceptual de la misma, no detalles técnicos.

Answer 1

bien, después de un poco de investigación y discusión, aquí es lo que he aprendido:

Conceptualmente Un índice es una copia ordenada del campo de datos es la indexación, donde cada valor de índice apunta a que es original (sin clasificar) fila. Como la base de datos sabe cómo se ordenan los valores, puede aplicar algoritmos de búsqueda más sofisticados que solo buscar el valor de principio a fin. El binary search algorithm es un ejemplo simple de un algoritmo de búsqueda para listas ordenadas y reduce el tiempo máximo de búsqueda de O (n) a O (log n).

Como nota al margen: Un algoritmo de ordenación decente en general, se llevará a O (n log n) para completar, lo que significa (como todos hemos oído probablemente antes) que deberá colocar índices en campos que se buscará a menudo , ya que es un poco más caro agregar el índice (que incluye una clasificación) que realizar una búsqueda completa varias veces. Por ejemplo, en una gran base de datos de> 1,000,000 de entradas, está en el rango de 20 veces más costoso de ordenar que buscar una vez.

Editar: Consulte @Jarod Elliott's answer para ver con más detalle las eficiencias de búsqueda, específicamente en lo que respecta a las operaciones de lectura desde el disco.

Answer 2

Para continuar con la analogía de la parte posterior del libro, si las páginas eran en orden por ese elemento sería el mismo tiempo de búsqueda que una búsqueda no indexada, sí.

Sin embargo, ¿qué ocurre si su libro es una lista de reseñas de libros ordenadas por autor, pero solo conoce el ISBN. El ISBN es único, sí, pero igual tendrá que escanear cada revisión para encontrar la que está buscando.

Ahora, agregue un índice en la parte posterior del libro, ordenado por ISBN. Boom, tiempo de búsqueda rápido. Esto es análogo al índice de la base de datos, que va desde la clave de índice (ISBN) a la fila de datos reales (en este caso, un número de página de su libro).

Answer 3

Ampliando las eficiencias del algoritmo de búsqueda, un área clave en el rendimiento de la base de datos es qué tan rápido se puede acceder a los datos. En general, leer datos de un disco es mucho más lento que leer datos de la memoria.

Para ilustrar un punto, supongamos que todo está almacenado en el disco. Si necesita buscar en cada fila de datos en una tabla buscando ciertos valores en un campo, aún necesita leer toda la fila de datos del disco para ver si coincide, esto se conoce comúnmente como 'escaneo de tabla'. '.

Si su tabla es de 100MB, eso es 100MB, necesita leer desde el disco.

Si ahora indexa la columna que desea buscar, en términos simplistas, el índice almacenará cada valor único de los datos y una referencia a la ubicación exacta de la fila completa de datos correspondiente. Este índice ahora solo puede ser de 10 MB en comparación con 100 MB para toda la tabla.

Leer 10MB de datos del disco (y tal vez un poco más para leer los datos de fila completa para cada coincidencia) es aproximadamente 10 veces más rápido que leer los 100MB.

Diferentes bases de datos almacenarán índices o datos en la memoria de diferentes maneras para hacer estas cosas mucho más rápido. Sin embargo, si su conjunto de datos es grande y no cabe en la memoria, la velocidad del disco puede tener un gran impacto y la indexación puede mostrar grandes ganancias. En la memoria todavía puede haber grandes ganancias de rendimiento (entre otras eficiencias).

En general, es posible que no note ninguna diferencia tangible al indexar un pequeño conjunto de datos que cabe fácilmente en la memoria.

Los detalles subyacentes variarán entre los sistemas y en realidad serán mucho más complicados, pero siempre he encontrado que las lecturas del disco frente a las lecturas de memoria son una forma fácil de explicar esto.