¿Cómo funciona una tabla hash? Es más rápido que "SELECT * FROM .."

Question

Digamos, que tengo:

 
Key | Indexes | Key-values 
----+---------+------------ 
001 | 100001 | Alex 
002 | 100002 | Micheal 
003 | 100003 | Daniel 

digamos que queremos buscar 001, cómo hacer el proceso de búsqueda rápida usando tabla hash?

¿No es lo mismo que usamos el "SELECT * from .." en mysql? Leo mucho, dicen, la búsqueda "SELECT *" de principio a fin, pero ¿no es la tabla hash? ¿Porque y como?

Al utilizar la tabla hash, ¿estamos reduciendo los registros que estamos buscando? ¿Cómo?

¿Alguien puede demostrar cómo insertar y recuperar el proceso de la tabla hash en el código de consulta de MySQL? por ejemplo,

SELECT * from table1 where hash_value="bla" ... 

Otro escenario: Si los índices son como S0001, S0002, T0001, T0002, etc. En MySQL que podría utilizar:

SELECT * from table WHERE value = S* 

no es lo mismo y más rápido?

Answer 1

Una tabla hash simple funciona manteniendo los elementos en varias listas, en lugar de solo una. Utiliza un método muy rápido y repetible (es decir, no aleatorio) para elegir la lista para mantener cada elemento. Por lo tanto, cuando llega el momento de encontrar el elemento nuevamente, repite ese método para descubrir en qué lista buscar y luego realiza una búsqueda lineal normal (lenta) en esa lista.

Al dividir los elementos en 17 listas, la búsqueda se vuelve 17 veces más rápida, lo que es una buena mejora.

Aunque, por supuesto, esto solo es cierto si las listas tienen aproximadamente la misma longitud, por lo que es importante elegir un buen método para distribuir los elementos entre las listas.

En su tabla de ejemplo, la primera columna es la clave, lo que necesitamos para encontrar el elemento. Y supongamos que mantendremos 17 listas.Para insertar algo, realizamos una operación en la clave llamada hash. Esto solo convierte la llave en un número. No devuelve un número aleatorio, porque siempre debe devolver el mismo número para la misma clave. Pero al mismo tiempo, los números deben "extenderse" ampliamente.

Luego tomamos el número y el uso de módulo resultante para reducir su tamaño hasta el tamaño de nuestra lista:

Hash(key) % 17 

Todo esto sucede muy rápido. Nuestras listas están en una matriz, por lo que:

_lists[Hash(key % 17)].Add(record); 

Y más tarde, para encontrar el artículo utilizando esa clave:

Record found = _lists[Hash(key % 17)].Find(key); 

Tenga en cuenta que cada lista sólo puede ser cualquier tipo de contenedor, o una lista enlazada clase que escribes a mano. Cuando ejecutamos un Find en esa lista, funciona de manera lenta (examine la clave de cada registro).

Answer 2

Las tablas hash son ideales para localizar entradas en O (1) costo donde la clave (que se usa para hash) ya se conoce. Están en uso generalizado tanto en bibliotecas de colecciones como en motores de bases de datos. Debería poder encontrar mucha información sobre ellos en Internet. ¿Por qué no comienzas con Wikipedia o simplemente haces una búsqueda en Google?

No conozco los detalles de mysql. Si hay una estructura llamada "tabla hash", esa sería probablemente una especie de tabla que usa hash para ubicar las claves. Estoy seguro de que alguien más te contará sobre eso. =)

EDIT: (en respuesta a comentar)

Ok. Trataré de hacer una explicación extremadamente simplificada: Una tabla hash es una tabla donde las entradas se ubican en función de una función de la clave. Por ejemplo, diga que desea almacenar información sobre un conjunto de personas. Si lo almacena en una matriz ordenada sin clasificar, deberá iterar sobre los elementos en secuencia para encontrar la entrada que está buscando. En promedio, esto necesitará comparaciones N/2.

Si, en cambio, coloca todas las entradas en los índices en función del primer carácter del nombre de las personas. (A = 0, B = 1, C = 2, etc.), inmediatamente podrá encontrar la entrada correcta siempre que sepa el primer nombre. Esta es la idea básica. Probablemente se dé cuenta de que se requiere un manejo especial (reajuste, o permitir listas de entradas) para admitir entradas múltiples que tengan la misma primera letra. Si tiene una tabla hash bien dimensionada, debería poder ir directamente al elemento que está buscando. Esto significa aproximadamente una comparación, con el descargo de responsabilidad del manejo especial que acabo de mencionar.

Answer 3

Supongo que podría usar una función hash para obtener la ID que desea seleccionar. Al igual que

SELECT * FROM tabla WHERE = valor hash_fn (whatever_input_you_build_your_hash_value_from)

entonces no necesitan saber el id de la fila que desea seleccionar y puede hacer una consulta exacta. Como sabes que la fila siempre tendrá la misma identificación debido a la entrada, construyes la forma del valor hash y siempre puedes volver a crear esta identificación a través de la función hash.

Sin embargo, esto no siempre es cierto dependiendo del tamaño de la tabla y la cantidad máxima de valores hash (a menudo tiene "X mod hash-table-size" en algún lugar de su hash). Para solucionar esto, debe tener una estrategia determinista que utilice cada vez que obtenga dos valores con la misma ID. Debería consultar Wikipedia para obtener más información sobre esta estrategia, su manejo de colisiones y debe mencionarse en el mismo artículo que hash-tables.

MySQL probablemente usa hashtables en alguna parte debido a la característica O (1) que se menciona norheim.se (arriba).

Answer 4

No se preocupe por lo que MySQL está haciendo internamente para localizar registros rápidamente. El trabajo de una base de datos es hacer ese tipo de cosas por ti. Simplemente ejecute una consulta SELECT [columns] FROM table WHERE [condition]; y deje que la base de datos genere un plan de consulta para usted. Tenga en cuenta que no desea utilizar SELECT *, ya que si alguna vez agrega una columna a la tabla que romperá todas las consultas anteriores que dependían de que haya un cierto número de columnas en un orden determinado.

Si realmente quiere saber lo que está pasando bajo el capó (es bueno saber, pero no implementarla uno mismo: ese es el propósito de una base de datos), lo que necesita saber lo que los índices son y cómo trabajan. Si una tabla no tiene ningún índice en las columnas involucradas en la cláusula WHERE, entonces, como dices, la base de datos tendrá que buscar en cada fila de la tabla para encontrar las que coincidan con tu condición. Pero si hay un índice , la base de datos buscará en el índice para encontrar la ubicación exacta de las filas que desea, y saltará directamente a ellas. Los índices generalmente se implementan como B+-trees, un tipo de árbol de búsqueda que utiliza muy pocas comparaciones para ubicar un elemento específico. La búsqueda de un árbol B para una clave específica es muy rápida. MySQL también es capaz de usar índices hash, pero estos tienden a ser más lentos para los usos de la base de datos. Los índices hash normalmente solo funcionan bien en teclas largas (especialmente cadenas de caracteres), ya que reducen el tamaño de la clave a un tamaño de hash fijo. Para tipos de datos como números enteros y números reales, que tienen un orden bien definido y una longitud fija, la facilidad de búsqueda de un árbol B generalmente proporciona un mejor rendimiento.

Quizás desee consultar los capítulos en MySQL manual y PostgreSQL manual sobre la indexación.

Answer 5

http://en.wikipedia.org/wiki/Hash_table

Las tablas hash se pueden usar como estructuras de datos en memoria. Las tablas hash también pueden adoptarse para su uso con estructuras de datos persistentes; database indices a veces utilizan estructuras de datos basadas en disco basadas en tablas hash, aunque balanced trees son más populares.