Mi conocimiento de bases de datos y SQL se basa principalmente en clases universitarias. De todos modos, pasé unos pocos meses (casi un año) en una empresa, donde trabajaba con bases de datos.
He leído algunos libros y he participado en unos entrenamientos sobre bases de datos como MySQL, PostgreSQL, SQLite, Oracley también unos nonSQL dbs como nosotros MongoDB, Redis, ElasticSearchetc.
Como dije, soy un principiante, con mucha falta de conocimiento, pero hoy, alguien dijo algo, lo que está totalmente en contra de mi conocimiento del principiante.
Dejame explicar. Tomemos una base de datos SQL y creemos una tabla simple Personcon pocos registros dentro:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23Ahora, es la parte en la que me gustaría centrarme, ides la INDEX.
Hasta ahora, pensé que funcionaba de esta manera: cuando se crea una tabla, la INDEX está vacía. Cuando agrego un nuevo registro a mi tabla, el INDEXcálculo se vuelve a calcular en función de algunos resultados. Por ejemplo:
Agrupando uno por uno:
1 ... N
N+1 ... 2N
...
XN+1 ... (X+1)Nentonces, para mi ejemplo con size = 11 elementsy N = 3será así:
id | name | age
-----------------
1 | Alex | 24 // group0
2 | Brad | 34 // group0
3 | Chris | 29 // group0
4 | David | 28 // group1
5 | Eric | 18 // group1
6 | Fred | 42 // group1
7 | Greg | 65 // group2
8 | Hubert | 53 // group2
9 | Irvin | 17 // group2
10 | John | 19 // group3
11 | Karl | 23 // group3Entonces, cuando estoy usando la consulta SELECT * FROM Person WHERE id = 8, hará un cálculo simple 8 / 3 = 2, por lo que debemos buscar este objeto group2y luego se devolverá esta fila:
8 | Hubert | 53
Este enfoque funciona a tiempo O(k)donde k << size. Por supuesto, un algoritmo para organizar filas en grupos es mucho más complicado, pero creo que este simple ejemplo muestra mi punto de vista.
Así que ahora, me gustaría presentar otro enfoque, que me han mostrado hoy.
Tomemos nuevamente esta tabla:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23Ahora, estamos creando algo similar a Hashmap(de hecho, literalmente es un Hash Map) que se asigna ida la addressfila con esta identificación. Digamos:
id | addr
---------
1 | @0001
2 | @0010
3 | @0011
4 | @0100
5 | @0101
6 | @0110
7 | @0111
8 | @1000
9 | @1001
10 | @1010
11 | @1011Entonces, cuando estoy ejecutando mi consulta: SELECT * FROM Person WHERE id = 8
se asignará directamente id = 8a la dirección en la memoria y se devolverá la fila. Por supuesto, la complejidad de esto esO(1) .
Así que ahora tengo algunas preguntas.
1. ¿Cuáles son las ventajas y desventajas de ambas soluciones?
2. ¿Cuál es más popular en las implementaciones de bases de datos actuales? ¿Quizás diferentes dbs usan diferentes enfoques?
3. ¿Existe en dbs no SQL?
Gracias de antemano
COMPARACIÓN
| B-tree | Hash Table
----------------------------------------------------
---------------- one element -------------------
----------------------------------------------------
SEARCHING | O(log(N)) | O(1) -> O(N)
DELETING | O(log(N)) | O(1) -> O(N)
INSERTING | O(log(N)) | O(1) -> O(N)
SPACE | O(N) | O(N)
----------------------------------------------------
---------------- k elements -------------------
----------------------------------------------------
SEARCHING | k + O(log(N)) | k * O(1) -> k * O(N)
DELETING | k + O(log(N)) | k * O(1) -> k * O(N)
INSERTING | k + O(log(N)) | k * O(1) -> k * O(N)
SPACE | O(N) | O(N)N - número de registros
Estoy en lo cierto? ¿Qué pasa con el costo de reconstruir la tabla B-tree y Hash después de cada inserción / eliminación ? En el caso del árbol B, tenemos que cambiar algunos punteros, pero en el caso del árbol B equilibrado, se necesita más esfuerzo. También en el caso de la tabla Hash , tenemos que hacer pocas operaciones, especialmente si nuestra operación genera conflictos .
O(1)ti lo hizo bien! En la primera forma, parece que estás describiendo un índice de árbol B pero tienes algunos malentendidos. No hay cálculo (división por 3 ni nada), es más complejo ya que el árbol tiene más niveles (es un árbol, tiene ramas grandes, pequeñas y más pequeñas, ..., y luego se va :)Of course, an alghoritm to organise rows in groups is for sure much more complicated but I think this simple example shows my point of view.Por supuesto, sé que es mucho mucho más complicado. Finalmente, cuando digo en mi códigoINDEXcuál de mis soluciones ( 1ra o 2da ) está más cerca de esta real? Y en cuanto al tiempo necesario para acceder a un registro basado enINDEX. ¿Es realmenteO(1)? Con el índice B-tree se parece muchoO(log2(N)). Estoy en lo cierto?Respuestas:
Básicamente, estás describiendo un índice de árbol B y un índice hash. Ambos tienen un lugar, pero ambos son los más adecuados para diferentes trabajos.
Ventajas y desventajas
Los índices B-tree (y B + -tree) suelen estar equilibrados. Esto significa que buscar un valor siempre tomará la misma cantidad de tiempo sin importar en qué parte del árbol caiga (O (log n)). En general, el número de niveles en el árbol es limitado, por lo que tiende a ser "más amplio", no "más profundo". Sin embargo, para conjuntos de datos pequeños, el costo de mantener y usar el árbol B puede ser más que solo leer todas las filas. Los índices de árbol B son buenos para conjuntos de datos grandes, conjuntos de datos con baja selectividad o conjuntos de datos en los que tiene la intención de seleccionar un rango de objetos, no solo un objeto.
Las tablas hash son excelentes para pequeños conjuntos de datos. Los índices de hash tienen un número predefinido de depósitos de hash, según el algoritmo de hash utilizado. Esto se debe a que un algoritmo de hash dado solo puede producir tantos hashes únicos, por lo que solo se vuelve "más profundo", no "más ancho". Una vez que el motor de la base de datos encuentra el depósito correcto, recorre todos los objetos en ese depósito para encontrar el que desea. Con conjuntos de datos pequeños y altamente selectivos, cada depósito contiene un número muy pequeño de objetos y se resuelve con bastante rapidez. Con conjuntos de datos más grandes, los cubos se llenan mucho más. Entonces, si el objeto que necesita está en un cubo pequeño o está cerca del comienzo del cubo, regresa bastante rápido. Si está al final de un cubo grande, lleva más tiempo. El índice no está equilibrado, por lo que el rendimiento varía entre O (1) y O (n).
Popularidad
En general, me he encontrado con los árboles B más. Los índices de mapa de bits también son otra opción para valores con baja cardinalidad (piense en booleanos o tal vez género). Esto variará dependiendo de su motor de base de datos en cuanto a qué tipos de índice están disponibles.
NoSQL
Las bases de datos NoSQL definitivamente admiten índices. La mayoría admite B-tree o una variación de B-tree. La mayoría parece admitir índices hash también.
fuente
¿Cuáles son las ventajas y desventajas de ambas soluciones? La segunda solución no puede realizar escaneos de rango. Es ideal para seleccionar una sola identificación. Pero, ¿qué pasa si quieres identificadores 3 a 8? Tiene que tomar todos los registros individuales que en el mundo real no son solo O (1) * 6 registros para recuperar. En una gran base de datos de producción con un índice HashMap, obtendría registros en diferentes páginas, lo que requeriría que golpee el disco y lea seis páginas diferentes en la memoria.
En una estructura B-Tree, como cómo se implementaría realmente su primera situación, los identificadores serían secuenciales en el disco y una sola página probablemente contendría identificadores 3 - 8 aumentando la velocidad de los escaneos de rango haciendo acceso individual O (log n) .
¿Cuál es más popular en las implementaciones de bases de datos actuales? ¿Quizás diferentes dbs usan diferentes enfoques? No tengo una gran experiencia en muchas bases de datos diferentes. Sé que Sql Server usa B-Trees principalmente, pero SQl 2014 tiene algunos nuevos índices Hash que puede usar en ciertas tablas. Escucho que muchas bases de datos No Sql y bases de datos de almacenamiento en caché basadas en la recuperación de registros individuales también usan índices hash. Esto tiene sentido para los cachés ya que desea el registro para el usuario A Página 11 y no necesita escaneos de rango.
¿Existe en dbs no SQL? Sí. Echando un vistazo rápido a la documentación de creación de índice para postgressql, veo que es compatible con los índices Hash y B-Tree, así como con algunos otros.
fuente