mysql - create - postgresql index integer

Uso de Postgres de los índices btree vs MySQL B+trees (3)

En las bases de datos a menudo tiene consultas que entregan algunos rangos de datos, como identificadores de 100 a 200.
En este caso

B-Tree debe seguir la ruta desde la raíz a las hojas de cada entrada para obtener el indicador de datos.
B + -Los arboles pueden "caminar" a través de las hojas y deben seguir el camino a las hojas solo la primera vez (es decir, para la identificación 100)

Esto se debe a que B + -Trees almacena solo los datos (o puntero de datos) en las hojas y las hojas están vinculadas para que pueda realizar un recorrido rápido en el orden.

B + -tree

Otro punto es:
En B + Trees, los nodos internos almacenan solo el puntero a otros nodos sin ningún puntero de datos, por lo que tiene más espacio para los punteros y necesita menos operaciones IO y puede almacenar más punteros de nodo en una página de memoria.

Así que para consultas de rango B + -Los arboles son la estructura de datos óptima. Para selecciones individuales, los árboles B podrían ser mejores (causas de la profundidad / tamaño del árbol), ya que los indicadores de datos se encuentran también dentro del árbol.

Estamos en el proceso de migrar de MySQL a PGSQL y tenemos una tabla de 100 millones de filas.

Cuando intentaba determinar cuánto espacio utilizan ambos sistemas, encontré mucha menos diferencia para las tablas, pero encontré enormes diferencias para los índices.

Los índices de MySQL ocupaban más tamaño que los datos de la tabla y postgres utilizaba tamaños considerablemente menores.

Al investigar por la razón, encontré que MySQL usa árboles B + para almacenar los índices y postgres uses árboles B.
El uso de MySQL de los índices fue un poco diferente, almacena los datos junto con los índices (debido a que el aumento de tamaño), pero postgres no.

Ahora las preguntas:

Al comparar el árbol B y los árboles B + en la base de datos, es mejor usar árboles B + ya que son mejores para las consultas de rango O (m) + O (logN): ¿donde m en el rango y la búsqueda es logarítmica en árboles B +?
Ahora, en los árboles B, la búsqueda es logarítmica para las consultas de rango que dispara hasta O (N), ya que no tiene la lista vinculada de la estructura subyacente para los nodos de datos. Dicho esto, ¿por qué postgres utiliza árboles B? ¿Se desempeña bien para las consultas de rango (lo hace, pero cómo se maneja internamente con árboles B)?
La pregunta anterior es desde el punto de vista de postgres, pero desde una perspectiva de MySQL, ¿por qué utiliza más almacenamiento que postgres? ¿Cuál es el beneficio de rendimiento de usar árboles B + en realidad?

Podría haber pasado por alto / malinterpretado muchas cosas, así que siéntase libre de corregir mi entendimiento aquí.

Editar para responder a las preguntas de Rick James

Estoy usando el motor InnoDB para MySQL
Construí el índice después de rellenar los datos, de la misma manera que lo hice en postgres
Los índices no son índices ÚNICOS, solo índices normales
No hubo inserciones aleatorias, utilicé csv cargando tanto en postgres como en MySQL y solo después de esto creé los índices.
El tamaño de bloque de Postgres para los índices y los datos es de 8 KB, no estoy seguro de MySQL, pero no lo cambié, por lo que deben ser los valores predeterminados.
No llamaría grandes a las filas, tienen alrededor de 4 campos de texto con 200 caracteres de longitud, 4 campos decimales y 2 campos de bigint - 19 números de longitud.
El PK es una columna bigint con 19 números, no estoy seguro de si esto es voluminoso? ¿En qué escala debe diferenciarse voluminoso frente a no voluminoso?
El tamaño de la tabla de MySQL fue de 600 MB y el de Postgres fue de aproximadamente 310 MB, ambos índices incluidos. Esto equivale a un tamaño un 48% más grande si mi cálculo es correcto. Eso puede llevar a mejores números, supongo.
Información de la máquina: Tenía suficiente RAM: 256 GB para que encajaran todas las tablas e índices, pero no creo que tengamos que atravesar esta ruta en absoluto, no vi ninguna diferencia de rendimiento notable en ambos.

Preguntas adicionales

Cuando decimos que ocurre la fragmentación? ¿Hay alguna forma de deshacer la fragmentación para que podamos decir que más allá de esto, no hay nada que hacer? Por cierto, estoy usando Cent OS.
¿Hay una manera de medir el tamaño del índice en MySQL, ignorando la clave principal ya que está agrupada, de modo que podamos ver qué tipo está ocupando más tamaño si es que hay alguno?

MySQL y PostgreSQL no son realmente comparables aquí. Innodb usa un índice para almacenar datos de tablas (y los índices secundarios solo apuntan a la tecla p). Esto es ideal para búsquedas de pkey de una sola fila y con árboles B +, hazlo bien con las consultas de rango en el campo pkey, pero presenta desventajas de rendimiento para todo lo demás.

PostgreSQL usa tablas de montón y pone los índices como separados. Es compatible con una serie de algoritmos de indexación diferentes. Dependiendo de su consulta de rango, es posible que un índice btree no le ayude y que, en su lugar, necesite un índice GiST. De manera similar, los índices GIN funcionan bien con las búsquedas de miembros (para arreglos, fts, etc.).

Creo que se usa btree porque sobresale en el caso de uso simple: ¿qué huevas contienen los siguientes datos? Esto se convierte en un bloque de construcción de GIN, por ejemplo.

Pero no es cierto que PostgreSQL no puede usar árboles B +. GiST se basa en índices B + Tree en un formato generalizado. Por lo tanto, PostgreSQL te da la opción de usar árboles B + donde sea útil.

Primero, y lo más importante, si no está utilizando InnoDB , cierre esta pregunta, vuelva a generar con InnoDB, luego vea si necesita volver a abrir la pregunta. MyISAM no es preferido y no debe ser discutido.

¿Cómo construiste los índices en MySQL? Hay varias formas de generar índices de forma explícita o implícita; conducen a un mejor o peor embalaje.

MySQL: los datos y los índices se almacenan en árboles B + compuestos de bloques de 16 KB .

MySQL: los índices UNIQUE (incluida la PRIMARY KEY ) deben actualizarse al insertar filas. Por lo tanto, un índice UNIQUE necesariamente tendrá muchas divisiones de bloque, etc.

MySQL: La PRIMARY KEY está agrupada con los datos, por lo que efectivamente ocupa cero espacio. Si carga los datos en orden PK, la fragmentación del bloque es mínima.

Las claves secundarias no UNIQUE pueden construirse sobre la marcha, lo que conduce a cierta fragmentación. O se pueden construir después de cargar la tabla; esto conduce a un embalaje más denso.

Las claves secundarias ( UNIQUE o no) incluyen implícitamente la PRIMARY KEY en ellas. Si el PK es "grande", entonces las claves secundarias son voluminosas. ¿Cuál es tu PK? ¿Es esta la ''respuesta''?

En teoría, las inserciones totalmente aleatorias en un BTree llevan a que los bloques se llenen aproximadamente en un 69% . Tal vez esta es la respuesta. ¿Es MySQL un 45% más grande (1/69%)?

Con las filas de 100M, probablemente muchas operaciones estén vinculadas a E / S porque no tiene suficiente RAM para almacenar en caché todos los datos y / o bloques de índice necesarios. Si todo está en caché, entonces B-Tree contra B + Tree no hará mucha diferencia. Analicemos lo que debe suceder para una consulta de rango cuando las cosas no están completamente almacenadas en caché.

Con cualquier tipo de árbol, la operación comienza con un desglose en el árbol. Para MySQL, las filas de 100M tendrán un árbol B + de aproximadamente 4 niveles de profundidad. Los 3 nodos que no son hojas (de nuevo bloques de 16KB) se almacenarán en caché (si aún no lo estaban) y se reutilizarán. Incluso para Postgres, este almacenamiento en caché probablemente se produce. (No sé Postgres.) Entonces comienza el escaneo de rango. Con MySQL recorre el resto del bloque. (Regla de oro: 100 filas en un bloque). ¿Lo mismo para Postgres?

Al final del bloque tiene que pasar algo diferente. Para MySQL, hay un enlace al siguiente bloque. Ese bloque (con 100 filas más) se recupera del disco (si no se almacena en caché). Para un árbol B, los nodos que no son hojas deben atravesarse de nuevo. 2, probablemente 3 niveles todavía están en caché. Yo esperaría que la necesidad de otro nodo no hoja se recupere del disco solo 1 / 10K filas. (10K = 100 * 100) Es decir, Postgres podría golpear el disco 1% más a menudo que MySQL, incluso en un sistema "frío".

Por otro lado, si las filas son tan gruesas que solo 1 o 2 pueden caber en un bloque de 16K, el "100" que seguí usando es más como "2", y el 1% se convierte en un 50%. Es decir, si tienes filas grandes, esta podría ser la "respuesta" . ¿Lo es?

¿Cuál es el tamaño de bloque en Postgres? Tenga en cuenta que muchos de los cálculos anteriores dependen del tamaño relativo entre el bloque y los datos. ¿Podría ser esto una respuesta?

Conclusión: te he dado 4 posibles respuestas. ¿Le gustaría aumentar la pregunta para confirmar o refutar que cada uno de estos se aplica? (Existencia de índices secundarios, PK grande, construcción ineficiente de índices secundarios, filas grandes, tamaño de bloque, ...)

Addenda sobre CLAVE PRIMARIA

Para InnoDB, otra cosa a tener en cuenta ... Es mejor tener una PRIMARY KEY en la definición de la tabla antes de cargar los datos. También es mejor ordenar los datos en orden PK antes de LOAD DATA . Sin especificar ninguna PRIMARY KEY o UNIQUE , InnoDB crea una PK oculta de 6 bytes; esto suele ser sub-óptimo.