Árboles B e índices de bases de datos

¿Qué es un B-tree?

• El B-tree cumple un papel fundamental en mucho software, especialmente en los sistemas de gestión de bases de datos (DBMS)

• MySQL, Postgres, MongoDB y Dynamo dependen de los índices basados en B-tree para realizar búsquedas eficientes de datos

• Veremos cómo funcionan el B-tree y el B+tree, por qué las bases de datos los usan en los índices y por qué usar UUID como clave primaria puede ser una mala idea

• Un B-tree almacena pares de datos conocidos como clave y valor en una estructura que los programadores llaman similar a un árbol

• Un B-tree está compuesto por nodos (rectángulos) y punteros a hijos (líneas que conectan los nodos)

• Al nodo superior se le llama nodo raíz, a los nodos del nivel más bajo nodos hoja, y a todos los demás nodos internos

• Esta es la definición de un B-tree:

  • Cada nodo almacena N pares clave/valor (donde N es mayor que 1 y menor o igual a K)
  • Cada nodo interno tiene al menos N/2 pares clave/valor (un nodo interno no es hoja ni raíz)
  • Cada nodo tiene N+1 hijos
  • El nodo raíz tiene al menos un valor y dos hijos, a menos que sea el único nodo
  • Todas las hojas están en el mismo nivel

• Otra característica clave del B-tree es el ordenamiento. Dentro de cada nodo, los elementos se mantienen ordenados

• Gracias a ese ordenamiento, se puede buscar una clave de forma muy eficiente. La búsqueda comienza en el nodo raíz y sigue estos pasos:

  1. Verificar si la clave que se busca está contenida en el nodo
  2. Si no está, encontrar en el nodo la posición donde se insertaría la clave
  3. En ese punto, seguir el puntero a hijo hacia el siguiente nivel y repetir el proceso

• Al buscar de esta forma, solo hace falta visitar un nodo por cada nivel del árbol para encontrar una clave

• El B-tree fue diseñado específicamente para funcionar bien con cantidades muy grandes de datos que además deben persistir en almacenamiento de largo plazo (disco). La razón es que cada nodo usa una cantidad fija de bytes

• La cantidad de valores que puede almacenar cada nodo en un B-tree depende de los bytes asignados a ese nodo y de los bytes consumidos por cada par clave/valor

B+tree (optimizado para bases de datos)

• El B+tree es similar al B-tree, pero cambian las siguientes reglas:
  • Los pares clave/valor se almacenan solo en los nodos hoja
  • Los nodos no hoja solo almacenan claves y punteros a hijos asociados
• La implementación de B+tree en los índices de MySQL tiene dos reglas adicionales específicas:
  • Los nodos no hoja almacenan N punteros a hijos en lugar de N+1
  • Todos los nodos también incluyen punteros "siguiente" y "anterior", de modo que cada nivel del árbol también puede funcionar como una lista doblemente enlazada
• Hay dos razones por las que el B+tree se adapta mejor a las bases de datos:
  1. Como los nodos internos no necesitan almacenar valores, pueden contener más claves por nodo interno. Esto ayuda a reducir la profundidad del árbol
  2. Todos los valores se almacenan en el mismo nivel y pueden recorrerse en orden mediante la lista enlazada del nivel inferior

Cómo usa MySQL el B+tree

• MySQL soporta varios motores de almacenamiento, y el más usado es InnoDB, que depende en gran medida del B+tree
• De hecho, InnoDB depende tanto de él que almacena todos los datos de la tabla en un B+tree usando la clave primaria de la tabla como clave del árbol
• Cada vez que se crea una nueva tabla InnoDB, se debe definir una clave primaria
• MySQL crea un B+tree para cada tabla nueva, y el valor definido como clave primaria se convierte en la clave del árbol. El valor asociado son los datos del resto de las columnas de cada fila, y se almacenan solo en los nodos hoja
• El tamaño de cada nodo de este B+tree está configurado en 16k por defecto
• Cada vez que MySQL necesita acceder a un fragmento de datos (clave, valor, etc.), carga desde disco la página completa asociada (el nodo del B+tree), incluso si no necesita las demás claves o valores
• También es común crear índices secundarios en una tabla InnoDB. Para cada índice secundario, se construye un B+tree persistente adicional, donde la clave es la columna que el usuario eligió indexar y el valor es la clave primaria de la fila asociada

Elección de clave primaria: inserciones

• Como la forma en que los datos de una tabla se ordenan dentro del B+tree depende de la clave elegida, la elección de PRIMARY KEY afecta el diseño en disco de todos los datos de la tabla
• Dos opciones comunes para clave primaria son:
  • una secuencia entera (BIGINT UNSIGNED AUTO_INCREMENT, por ejemplo)
  • UUID (del que existen varias versiones)
• Si se usa una clave primaria UUIDv4, al insertar ocurren estas consecuencias:
  1. No se puede predecir de antemano qué nodos se visitarán para insertar
  2. No se puede predecir qué nodo hoja será el destino de la inserción
  3. Los valores de las hojas no quedan ordenados
• Los problemas 1 y 2 aparecen porque, a lo largo de muchas inserciones, se deben visitar muchos nodos (páginas) del árbol. Ese exceso de lecturas y escrituras termina degradando el rendimiento
• Si se usa BIGINT UNSIGNED AUTO_INCREMENT como clave primaria:
  1. Cada nuevo valor insertado siempre sigue la ruta más a la derecha
  2. Las hojas solo se agregan del lado derecho del árbol
  3. En el nivel de hojas, los datos quedan ordenados según el orden de inserción
• Debido a los puntos 1 y 2, muchas inserciones secuenciales vuelven a recorrer la misma ruta de páginas, lo que reduce las solicitudes de I/O cuando se insertan muchos pares clave/valor

Elección de clave primaria: lectura secuencial de datos

• Es común recuperar datos en orden temporal dentro de una base de datos
• Si se usa UUIDv4 como clave primaria, la secuencia de valores del resultado de búsqueda queda dispersa entre múltiples nodos hoja no secuenciales
• Si se buscan valores insertados secuencialmente, todas las páginas que contienen el resultado estarán unas junto a otras. Al recuperar varias filas, incluso podría ocurrir que todas estén contiguas dentro de una sola página
• Para este patrón de consultas, usar una clave primaria secuencial puede reducir la cantidad de páginas que es necesario leer

Elección de clave primaria: tamaño

• El tamaño de la clave primaria también es una consideración importante. La clave primaria siempre debe:
  1. Ser lo suficientemente grande como para no agotarse
  2. Ser lo suficientemente pequeña como para no usar espacio de almacenamiento excesivo
• En secuencias enteras, una tabla más pequeña puede usar MEDIUMINT (16 millones de valores únicos) o INT (4 mil millones de valores únicos)
• Para tablas grandes, se usa BIGINT para ir a la segura (1.8e19 valores posibles). BIGINT tiene 64 bits (8 bytes)
• UUID normalmente tiene 128 bits (16 bytes), el doble del tipo entero más grande de MySQL
• Como los nodos del B+tree tienen tamaño fijo, usar BIGINT permite meter más claves por nodo que UUID. Eso produce árboles menos profundos y búsquedas más rápidas

B+tree, páginas e InnoDB

• Una de las grandes ventajas del B+tree es que se puede definir el tamaño de sus nodos como se quiera
• En InnoDB, los nodos del B+tree normalmente se configuran con 16k, que es el tamaño de una página de InnoDB
• Durante el procesamiento de consultas (y por lo tanto el recorrido del B+tree), InnoDB no lee filas y columnas individuales desde disco. Cada vez que necesita acceder a un dato, carga la página completa relacionada desde disco
• InnoDB tiene algunas técnicas para mitigar esto, y la principal es el buffer pool. El buffer pool es una caché en memoria para páginas de InnoDB que se ubica entre las páginas del disco y la ejecución de consultas de MySQL
• Cuando MySQL necesita leer una página, primero revisa si ya está en el buffer pool. Si está, la lee desde ahí y se salta la operación de I/O en disco. Si no está, busca la página en disco, la agrega al buffer pool y luego continúa con la ejecución de la consulta
• El buffer pool mejora enormemente el rendimiento de las consultas. Sin él, habría que hacer muchas más operaciones de I/O en disco para manejar la carga de consultas

Otros casos

• Aquí nos enfocamos principalmente en comparar claves secuenciales con claves aleatorias/UUID, pero estos principios son útiles de recordar sin importar el tipo de clave primaria o secundaria que se esté evaluando
• Por ejemplo, podría considerarse usar el timestamp user.created_at como clave de índice, ya que tiene características similares a un entero secuencial. A menos que se inserten datos históricos, las inserciones por lo general siempre avanzarán por la ruta más a la derecha
• En cambio, algo como la cadena user.email_address se parece más a una clave aleatoria. Como los usuarios no crean cuentas siguiendo el orden alfabético de sus correos, las inserciones se distribuyen por todo el B+tree

Conclusión

• Se cubrieron muchos aspectos sobre B+tree, índices y elección de claves primarias
• A simple vista puede parecer algo sencillo, pero hay matices importantes que deben considerarse para sacar el máximo rendimiento posible de una base de datos
• Para experimentar más, puedes visitar este sitio interactivo sobre B+tree

[GN⁺]

Comentarios de Hacker News

• Mantengo la wiki útil usando una estrategia para gestionarla como un B-Tree

  • Cuando hay demasiadas landing pages, muevo enlaces y secciones a subpáginas
  • Los enlaces similares y antiguos los muevo a páginas hermanas según el tema
  • Al final, los documentos antiguos terminan tres niveles por debajo de la landing page
  • La documentación termina siendo un problema de búsqueda
  • Es una buena manera de pasar productivamente una tarde de viernes

• Llevaba mucho tiempo buscando algo así, es una publicación increíble

  • Ojalá hubiera una sección sobre índices compuestos

• Gracias por el increíble material visual

  • Trabajé en soporte de indexación BTree+ sobre Aerospike
  • Quitar claves expiradas de BTree+ fue un desafío
  • Decidimos fusionar una bifurcación de un nivel solo dentro del primer nodo hoja hermano
  • Agregamos sharding sobre BTree+ para acelerar y reducir la contención de locks
  • Durante la limpieza, BTree+ puede quedar desbalanceado
  • Ofrecimos una función de reconstrucción de índices para evitar trabajo adicional de limpieza

• El modal de cookies no funciona en Firefox móvil

  • Deberían permitir que el usuario lo configure desde el navegador

• No deberías usar una columna UUID como clave primaria

  • Tienes que copiar un int de 128 bits en todos los aspectos relacionales
  • En la mayoría de los casos es completamente aleatorio
  • Para relaciones internas entre tablas, deberías usar un PK bigserial (64 bits), y usar UUID (128 bits) para identificadores a nivel de aplicación y claves naturales
  • La base de datos será mucho más feliz

• Es un excelente material educativo

  • Este tipo de demos interactivos ayuda muchísimo

• Si los bloques de disco y los nodos del B-tree son de 16k, y la clave, el valor y los punteros a hijos son todos de 8 bits, se pueden almacenar 682 pares clave/valor y 683 punteros a hijos por nodo

  • Un árbol de tres niveles puede almacenar más de 300 millones de pares clave/valor
  • Cada elemento tendría que ser de 8 bytes

• Es un gran artículo

  • InnoDB llama índice clustered a guardar los datos dentro del propio B-tree
  • MyISAM era un índice no clustered
  • Oracle y otros permiten elegir

• Pregunta qué significan v0, v1, ...v10 en el gráfico

  • Se pregunta si significan páginas diferentes

• Es una visualización interactiva hermosa

  • Está al más alto nivel en términos de educación y divulgación