En inglés simple, ¿a qué se parece más el índice de una base de datos? [duplicar]

13

Configuración : suponga que está enseñando una introducción a la clase Bases de datos, los estudiantes son estudiantes de CS que tienen un conocimiento práctico de las estructuras de árbol, cómo pueden acelerar las búsquedas y probablemente han implementado algunos en su vida.

Pregunta : ¿Cómo describiría la forma en que una base de datos utiliza índices para buscar en una tabla un conjunto de claves? ¿A qué estructura es más similar un índice de base de datos?

Bonificación : ¿Cómo alguien escribe una consulta SQL donde la cláusula aproveche la capacidad de búsqueda del índice que diseñan en una tabla determinada?

Las respuestas deben corresponder a todos los productos de base de datos en su conjunto. Estoy buscando consejos generales que permitan una búsqueda más rápida en todas las bases de datos. Descripciones simples en inglés por favor, sin código, las descripciones de búsqueda en Big O están bien. Esta pregunta podría ser demasiado específica para este sitio, consideré la posibilidad de solicitar StackExchange, pero como solicito una descripción simple en inglés de un concepto amplio, pensé que este sitio estaría bien.

    
pregunta wfoster 09.04.2013 - 16:26

6 respuestas

30

Los índices de la base de datos se modelan después de los índices de los libros de texto, y luego se hacen más eficientes:

Laspartessinsangríasonlaparteprincipalenlaqueestásbuscando,ylaparteconsangríadebajodealgunasdeellasidentificaaúnmástemasespecíficos.Cadaniveldesangradoessimilaraotracolumnaenelíndice.

Aprovecharlosíndiceses(creo)parcialmenteespecíficodelaimplementación.Porejemplo:

  • Siconsultalacolumnafoodpara"chicken" , se utilizará el índice.
  • Para "chick%" , diría que depende de la base de datos / tipo de índice, aunque todos los que conozco seguirán utilizándolo.
  • Se aplican reglas similares para consultar las columnas food y drink para "chicken" y "water" : primero limita los resultados según la primera columna del índice, luego la segunda, como si usara el índice externo , luego el índice sangrado, en un libro de texto.
  • Igualmente para "chik%" y "wat%"
  • Sin embargo, no se puede buscar "%ken" en un índice en las bases de datos que conozco, porque se indexan desde el principio de la palabra, no desde atrás, lo mismo que los índices de los libros de texto. Así que la base de datos tendrá que escanear toda la tabla.
respondido por el Izkata 09.04.2013 - 16:34
10

Quiero decir, es más similar a un índice. En lugar de hurgar en todo el libro, lo busca en el índice y encuentra la página en la que se encuentra.

La magia funciona porque el índice está organizado de una manera más fácil de buscar que el libro, es decir, alfabéticamente.

    
respondido por el djechlin 09.04.2013 - 16:33
7

Tome un libro, cualquier libro técnico.

Ir al final, donde hay un ... Índice.

¿Por qué está ahí? La misma razón para el DB. Por lo tanto, no tiene que buscar en un libro completo para una entrada específica.

Piensa en un diccionario. Es un índice de palabras, ordenadas alfabéticamente.

    
respondido por el Oded 09.04.2013 - 16:34
2

Suponiendo que la audiencia realmente tenga "un conocimiento práctico de las estructuras de los árboles, cómo pueden acelerar las búsquedas" (y, por lo tanto, el "inglés simple" no es lo que necesitan):

Un índice DB es un árbol B que usa los valores de una o más columnas (tuplas en el caso de varias columnas) como claves y referencias a los registros correspondientes como valores.

Un B-Tree es un árbol de búsqueda con un grado de bifurcación muy alto que está optimizado para la localidad de los datos y, por lo tanto, sigue funcionando bien cuando es demasiado grande como para mantenerlo en la RAM (y el acceso aleatorio se vuelve extremadamente caro).

A partir de esto, debe quedar claro que un índice solo puede ayudar a acelerar una consulta cuando la cláusula WHERE involucra a las columnas del índice en una condición de igualdad, una condición mayor / menor o especificando un prefijo (que usa el las columnas en el orden de sam aparecen en el índice, para índices de varias columnas), porque esas son las operaciones admitidas por un árbol de búsqueda.

    
respondido por el Michael Borgwardt 09.04.2013 - 17:14
1

No tiene que ser un b-tree, pero muchas bases de datos usan b-trees para implementar sus bases de datos. Cualquier cosa que desee saber sobre cómo funciona un índice y cuáles son sus características de rendimiento, puede averiguarlo estudiando los árboles b.

    
respondido por el Robert Harvey 09.04.2013 - 17:12
0

De Use el Índice Luke :

  

Un índice de base de datos es, después de todo, muy parecido al índice al final de un libro: ocupa su propio espacio, es altamente redundante y se refiere a la información real almacenada en un lugar diferente.

    
respondido por el Nemanja Trifunovic 09.04.2013 - 16:36

Lea otras preguntas en las etiquetas