5 respuestas en este tema

[jorgeu]

Ya que hablamos de índices quería compartir un poco sobre tipos de índices.

En la mayoría de los manejadores de bases de datos disponemos de los dos más importantes tipos de índices:

• Hash
• Btree

Hash
Utiliza algo parecido a las tablas hash para ubicar fácilmente registros dado un valor de los campos en el índice. Es ideal para cuando en los WHERE estaremos preguntando por un valor específico

Btree
Utiliza una estructura de árbol cuyos nodos tienen un arreglo de valores. Se puede conseguir sobre esta estructura como "Árbol B" en los libros de estructuras de datos. Es ideal para en los WHERE usaremos búsquedas ordenadas usando operadores > < >= <=. Normalmente es el tipo de índice por defecto.

Si elegimos bien los tipos de índice tenemos oportunidad de mejorar nuestro rendimiento.

Según la documentación lamentablemente en InnoDB sólo se tiene Btree y supuestamente MyISAM sí tiene índices BTREE. Me sorprendió!  (o es que yo confundía la ausencia de foreign keys con la ausencia de índices).

PostgreSQL tiene ambos pero sólo he usado BTree.

¿Qué me dices de otros manejadores que han usado?

Saludos

[eduarcol]

Hola a todos,

Hasta donde tengo entendido Firebird utiliza el B-Tree o alguna variacion de el no estoy 100% seguro al respecto, pero si se que no utiliza los Hash.

Algo que me toco aprender a la mala es que un indice sobre un campo ascendente no tiene ningun efecto si la consulta la devolvemos en forma descendente, por lo cual hay que crear ambos tipos en caso de necesitarlo.

Es el unico problema de rendimiento en Firebird y lo que me llevo a investigar al respecto, pero aparte de eso no he tenido necesidad de optimizacion de consultas y manejo de especificaciones de tipos de indices, me parece que Firebird hace muy bien su trabajo.

El que quiera conocer un poco mas a fondo Firebird Ann Harrison saco un manual muy bueno para conocer como trabaja el motor, lastima lo perdi y no he podido encontrar el enlace de nuevo.

[felipe]

Sería bueno ver algo de buenas prácticas para optimizar las consultas SQL.


Saludos!

[Marc]

Como han comentado Firebird solo tiene BTrees (actualmente permiten el recorrido en ambas direcciones, por lo que ya no hay que indexar el mismo campo en orden ascendente y descendente).

Los árboles BTree son muy buenos también para localizar valores únicos. No solo son óptimos para los rangos de valores. Es por eso que muchas bases de datos solo utilizan BTrees, puesto que no necesitan nada más.

Las tablas de Hash son demasiado sensibles a tener una función de hash bien balanceada. Sinceramente no me hago a la idea de como puede una base de datos definir por si sola una función de hash. Además tienen el enorme inconveniente de no poder hacer recorridos ordenados.

Sinceramente no veo la necesidad de índices Hash en las bases de datos (y creo que Firebird es un buen ejemplo de ello). Quizás alguien con más conocimientos pueda decir donde me equivoco.

[jorgeu]

Como han comentado Firebird solo tiene BTrees (actualmente permiten el recorrido en ambas direcciones, por lo que ya no hay que indexar el mismo campo en orden ascendente y descendente).

Los árboles BTree son muy buenos también para localizar valores únicos. No solo son óptimos para los rangos de valores. Es por eso que muchas bases de datos solo utilizan BTrees, puesto que no necesitan nada más.

Las tablas de Hash son demasiado sensibles a tener una función de hash bien balanceada. Sinceramente no me hago a la idea de como puede una base de datos definir por si sola una función de hash. Además tienen el enorme inconveniente de no poder hacer recorridos ordenados.

Sinceramente no veo la necesidad de índices Hash en las bases de datos (y creo que Firebird es un buen ejemplo de ello). Quizás alguien con más conocimientos pueda decir donde me equivoco.

Un post lleno de razón.

El Hash debería ser más rápido que B-Tree para valores únicos. Recuerda que el orden de las búsquedas en tablas Hash es constante en cambio en los Btree es M*log(N) donde M es el tamaño del nodo y N la cantidad de elementos.

Dejemos acá un paréntesis porque eso depende de la implementación

(en teoría) 

Saludos

[Marc]

Hola.

Un post lleno de razón.

El Hash debería ser más rápido que B-Tree para valores únicos. Recuerda que el orden de las búsquedas en tablas Hash es constante en cambio en los Btree es M*log(N) donde M es el tamaño del nodo y N la cantidad de elementos.

Dejemos acá un paréntesis porque eso depende de la implementación

(en teoría) 

Saludos

Me acuerdo que hablamos de esto cuando nos enseñaron el funcionamiento de los árboles binarios de búsqueda (Estructuras de Datos y Algoritmos fue de largo mi asignatura favorita).

En realidad eso que marcas son valores teóricos, los valores para búsquedas en memoria.

Pero en una situación real, en una base de datos, los datos (y los índices y las tablas de hash) no están en memoria sino en un disco duro y dada la enorme diferencia de tiempo entre el acceso a memoria y el acceso a disco, lo importante son los accesos a disco que vas a necesitar para recuperar la información.

Y los BTrees que usan los servidores SQL no son árboles binarios (aunque se siguen llamando así porqué su funcionamiento es el mismo), sino que se han diseñado específicamente para reducir al máximo los acceso a disco. Son árboles de búsqueda pero tienen k hijos cada nodo, tantos como elementos caben en un clúster de disco (ya que igualmente tendrás que leer todo un cluster, pues al menos que esté lleno de valores a comparar). Por eso el número de acceso a discos en un BTree de una servidor SQL ya no es del orden Log(N), sino Log en base k de N (con lo que estamos hablando de valores muchísimo menores, ya que creo que k suele ser del orden de 100).

Dado que lo realmente importante son el número de acceso a disco que necesitarás, puesto que es donde realmente se pierde tiempo (y no en las operaciones en memoria), y como usualmente solo se necesitan un par de accesos a disco (según creo recordar que nos comentó el profesor), el acceso a un índice BTree+ también se puede considerar en cierta forma constante (fíjate como en esas bases de datos, en la práctica aunque una tabla tenga millones de registros, siempre vas a tardar más o menos los mismos milisegundos en localizar un registro por su clave primaria, que después de todo no deja de ser un BTree como cualquier otro índice).

http://en.wikipedia.org/wiki/B%2B_tree

Saludos.