Hispanopedia Wiki
Articulo de referencia

Índice de mapa de bits

Un índice de mapa de bits es un tipo especial de índice de base de datos que utiliza mapas de bits . Los índices de mapa de bits se han considerado tradicionalmente adecuados pa...

Hispanopedia WikiContenido en espanolLectura gratuita

Un índice de mapa de bits es un tipo especial de índice de base de datos que utiliza mapas de bits .

Los índices de mapa de bits se han considerado tradicionalmente adecuados para columnas de baja cardinalidad , que tienen un número moderado de valores distintos, ya sea en términos absolutos o relativos al número de registros que contienen los datos. El caso extremo de baja cardinalidad son los datos booleanos (por ejemplo, ¿tiene acceso a internet un residente de una ciudad?), que tienen dos valores: verdadero y falso. Los índices de mapa de bits utilizan matrices de bits (comúnmente llamadas mapas de bits) y responden a las consultas realizando operaciones lógicas bit a bit sobre estos mapas de bits. Los índices de mapa de bits ofrecen una ventaja significativa en cuanto a espacio y rendimiento con respecto a otras estructuras para la consulta de este tipo de datos. Su desventaja radica en que son menos eficientes que los índices B-tree tradicionales para columnas cuyos datos se actualizan con frecuencia; por consiguiente, se emplean con mayor frecuencia en sistemas de solo lectura especializados en consultas rápidas, como los almacenes de datos, y generalmente no son adecuados para aplicaciones de procesamiento de transacciones en línea .

Algunos investigadores sostienen que los índices de mapa de bits también son útiles para datos de cardinalidad moderada o incluso alta (por ejemplo, datos con valores únicos) a los que se accede de forma de solo lectura, y las consultas acceden a múltiples columnas indexadas en mapas de bits utilizando ampliamente los operadores AND , OR o XOR . [ 1 ]

Los índices de mapa de bits también son útiles en aplicaciones de almacenamiento de datos para unir una tabla de hechos grande con tablas de dimensiones más pequeñas , como las que están organizadas en un esquema de estrella .

Ejemplo

Siguiendo con el ejemplo del acceso a Internet, un índice de mapa de bits puede visualizarse lógicamente de la siguiente manera:

A la izquierda, Identificador se refiere al número único asignado a cada residente, TieneInternet es el dato que se va a indexar, el contenido del índice de mapa de bits se muestra como dos columnas bajo el encabezado Mapas de bits . Cada columna en la ilustración de la izquierda bajo el encabezado Mapas de bits es un mapa de bits en el índice de mapa de bits. En este caso, hay dos mapas de bits de este tipo, uno para "tiene internet" Sí y otro para "tiene internet" No. Es fácil ver que cada bit en el mapa de bits Y muestra si una fila en particular se refiere a una persona que tiene acceso a internet. Esta es la forma más simple de índice de mapa de bits. La mayoría de las columnas tendrán más valores distintos. Por ejemplo, es probable que el monto de ventas tenga una cantidad mucho mayor de valores distintos. Las variaciones del índice de mapa de bits también pueden indexar estos datos de manera efectiva. Revisamos brevemente tres de estas variaciones.

Nota: Muchas de las referencias citadas aquí se revisan en ( John Wu (2007) ). [ 2 ] Para aquellos que puedan estar interesados ​​en experimentar con algunas de las ideas mencionadas aquí, muchas de ellas están implementadas en software de código abierto como FastBit, [ 3 ] la biblioteca C++ Lemur Bitmap Index , [ 4 ] la biblioteca Java Roaring Bitmap [ 5 ] y el sistema Apache Hive Data Warehouse.

Compresión

Por razones históricas, la compresión de mapas de bits y la compresión de listas invertidas se desarrollaron como líneas de investigación separadas, y solo más tarde se reconoció que resolvían esencialmente el mismo problema. [ 6 ]

El software puede comprimir cada mapa de bits en un índice de mapas de bits para ahorrar espacio. Se ha realizado una cantidad considerable de trabajo sobre este tema. [ 7 ] [ 8 ] Aunque hay excepciones como los mapas de bits Roaring, [ 9 ] Los algoritmos de compresión de mapas de bits suelen emplear codificación de longitud de ejecución , como el Código de Mapa de Bits Alineado por Bytes, [ 10 ] el código Híbrido Alineado por Palabras, [ 11 ] la compresión Híbrida Alineada por Palabras Particionada (PWAH), [ 12 ] el Híbrido Alineado por Palabras de Lista de Posiciones, [ 13 ] el Índice Adaptativo Comprimido (COMPAX), [ 14 ] el Híbrido Alineado por Palabras Mejorado (EWAH) [ 15 ] y el Conjunto de Enteros Composables 'N' Comprimido (CONCISE). [ 16 ] [ 17 ] Estos métodos de compresión requieren muy poco esfuerzo para comprimir y descomprimir. Más importante aún, los mapas de bits comprimidos con BBC, WAH, COMPAX, PLWAH, EWAH y CONCISE pueden participar directamente en operaciones bit a bit sin descompresión. Esto les confiere ventajas considerables sobre técnicas de compresión genéricas como LZ77 . La compresión BBC y sus derivados se utilizan en un sistema comercial de gestión de bases de datos . BBC es eficaz tanto para reducir el tamaño de los índices como para mantener el rendimiento de las consultas . BBC codifica los mapas de bits en bytes , mientras que WAH los codifica en palabras, lo que se ajusta mejor a las CPU actuales . "Tanto en datos sintéticos como en datos de aplicaciones reales, los nuevos esquemas alineados por palabras utilizan solo un 50 % más de espacio, pero realizan operaciones lógicas en datos comprimidos 12 veces más rápido que BBC." [ 18 ] Se informó que los mapas de bits PLWAH ocupan el 50 % del espacio de almacenamiento consumido por los mapas de bits WAH y ofrecen un rendimiento hasta un 20 % más rápido en operaciones lógicas . [ 13 ] Se pueden hacer consideraciones similares para CONCISE [ 17 ] y Enhanced Word-Aligned Hybrid. [ 15 ]

El rendimiento de esquemas como BBC, WAH, PLWAH, EWAH, COMPAX y CONCISE depende del orden de las filas. Una simple ordenación lexicográfica puede reducir el tamaño del índice a 9 y hacer que los índices sean varias veces más rápidos. [ 19 ] Cuanto mayor sea la tabla, más importante será ordenar las filas. También se han propuesto técnicas de reordenamiento para lograr los mismos resultados de ordenación al indexar datos en tiempo real. [ 14 ]

Codificación

Los índices de mapa de bits básicos utilizan un mapa de bits para cada valor distinto. Es posible reducir el número de mapas de bits utilizados mediante un método de codificación diferente. [ 20 ] [ 21 ] Por ejemplo, es posible codificar C valores distintos utilizando mapas de bits log(C) con codificación binaria . [ 22 ]

Esto reduce la cantidad de mapas de bits, ahorrando aún más espacio, pero para responder a cualquier consulta, es necesario acceder a la mayoría de ellos. Esto hace que potencialmente no sea tan eficaz como escanear una proyección vertical de los datos base, también conocida como vista materializada o índice de proyección. Encontrar el método de codificación óptimo que equilibre el rendimiento de las consultas (arbitrarias), el tamaño del índice y su mantenimiento sigue siendo un desafío.

Sin tener en cuenta la compresión, Chan e Ioannidis analizaron una clase de métodos de codificación multicomponente y llegaron a la conclusión de que la codificación de dos componentes se sitúa en el punto de inflexión de la curva de rendimiento frente al tamaño del índice y, por lo tanto, representa el mejor equilibrio entre el tamaño del índice y el rendimiento de las consultas. [ 20 ]

Clasificación

Para columnas de alta cardinalidad, es útil agrupar los valores, donde cada grupo abarca múltiples valores y se construyen mapas de bits para representar los valores en cada grupo. Este enfoque reduce la cantidad de mapas de bits utilizados, independientemente del método de codificación. [ 23 ] Sin embargo, los índices agrupados solo pueden responder a algunas consultas sin examinar los datos base. Por ejemplo, si un grupo cubre el rango de 0,1 a 0,2, entonces cuando el usuario solicita todos los valores menores que 0,15, todas las filas que caen en el grupo son posibles coincidencias y deben verificarse para comprobar si realmente son menores que 0,15. El proceso de comprobación de los datos base se conoce como comprobación de candidatos. En la mayoría de los casos, el tiempo empleado por la comprobación de candidatos es significativamente mayor que el tiempo necesario para trabajar con el índice de mapa de bits. Por lo tanto, los índices agrupados presentan un rendimiento irregular. Pueden ser muy rápidos para algunas consultas, pero mucho más lentos si la consulta no coincide exactamente con un grupo.

Historia

El concepto de índice de mapa de bits fue introducido por primera vez por el profesor Israel Spiegler y Rafi Maayan en su investigación "Consideraciones de almacenamiento y recuperación de bases de datos binarias", publicada en 1985. [ 24 ] El primer producto de base de datos comercial en implementar un índice de mapa de bits fue el Modelo 204 de Computer Corporation of America . Patrick O'Neil publicó un artículo sobre esta implementación en 1987. [ 25 ] Esta implementación es un híbrido entre el índice de mapa de bits básico (sin compresión) y la lista de identificadores de fila (lista RID). En general, el índice está organizado como un árbol B+ . Cuando la cardinalidad de la columna es baja, cada nodo hoja del árbol B contendría una larga lista de RID. En este caso, se requiere menos espacio para representar las listas RID como mapas de bits. Dado que cada mapa de bits representa un valor distinto, este es el índice de mapa de bits básico. A medida que aumenta la cardinalidad de las columnas, cada mapa de bits se vuelve disperso y puede requerir más espacio en disco que almacenar el mismo contenido como listas RID. En este caso, se opta por usar las listas RID, lo que lo convierte en un índice de árbol B+ . [ 26 ] [ 27 ]

Mapas de bits en memoria

Una de las razones más importantes para usar índices de mapa de bits es que los resultados intermedios que generan también son mapas de bits y pueden reutilizarse de manera eficiente en operaciones posteriores para responder a consultas más complejas. Muchos lenguajes de programación admiten esto como una estructura de datos de matriz de bits . Por ejemplo, Java tiene la BitSetclase y .NET tiene la clase BitArray . [ 28 ]

Algunos sistemas de bases de datos que no ofrecen índices de mapa de bits persistentes utilizan mapas de bits internamente para acelerar el procesamiento de consultas. Por ejemplo, las versiones 8.1 y posteriores de PostgreSQL implementan una optimización de "escaneo de índice de mapa de bits" para acelerar operaciones lógicas de complejidad arbitraria entre los índices disponibles en una sola tabla.

Para tablas con muchas columnas, el número total de índices distintos para satisfacer todas las consultas posibles (con condiciones de filtrado de igualdad en cualquiera de los campos) crece muy rápidamente, y se define mediante esta fórmula:

donorte[norte2]≡norte¡(norte−[norte2])¡[norte2]¡{\displaystyle \mathbf {C} _{n}^{\left[{\frac {n}{2}}\right]}\equiv {\frac {n!}{\left(n-\left[{\frac {n}{2}}\right]\right)!\left[{\frac {n}{2}}\right]!}}}. [ 29 ] [ 30 ]

Un escaneo de índice de mapa de bits combina expresiones en diferentes índices, lo que requiere solo un índice por columna para admitir todas las consultas posibles en una tabla.

Aplicar esta estrategia de acceso a los índices B-tree también puede combinar consultas de rango en varias columnas. En este enfoque, se crea un mapa de bits temporal en memoria con un bit por cada fila de la tabla (1 MB puede almacenar más de 8 millones de entradas). A continuación, los resultados de cada índice se combinan en el mapa de bits mediante operaciones bit a bit . Después de evaluar todas las condiciones, el mapa de bits contiene un "1" para las filas que coinciden con la expresión. Finalmente, se recorre el mapa de bits y se recuperan las filas coincidentes. Además de combinar índices de manera eficiente, esto también mejora la localidad de referencia de los accesos a la tabla, ya que todas las filas se obtienen secuencialmente de la tabla principal. [ 31 ] El mapa de bits interno se descarta después de la consulta. Si hay demasiadas filas en la tabla para usar 1 bit por fila, se crea un mapa de bits "con pérdida" en su lugar, con un solo bit por página de disco. En este caso, el mapa de bits solo se usa para determinar qué páginas obtener; luego, los criterios de filtro se aplican a todas las filas en las páginas coincidentes. 

Referencias

Notas
  1. ↑ Índice de mapa de bits frente a índice de árbol B: ¿Cuál y cuándo?, Vivek Sharma, Oracle Technical Network.
  2. ↑ John Wu (2007). "Referencias anotadas en el índice de mapas de bits" .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )
  3. ↑ "FastBit" . Archivado del original el 19 de septiembre de 2015. Consultado el 2 de febrero de 2011 .
  4. ↑ Biblioteca C++ de índice de mapas de bits de lémur
  5. ↑ Mapas de bits rugientes
  6. ↑ Jianguo Wang; Chunbin Lin; Yannis Papakonstantinou; Steven Swanson. "Un estudio experimental de la compresión de mapas de bits frente a la compresión de listas invertidas". Archivado el 7 de diciembre de 2019 en Wayback Machine . 2017. doi: 10.1145/3035918.3064007
  7. ↑ T. Johnson (1999). "Mediciones de rendimiento de índices de mapas de bits comprimidos" (PDF) . En Malcolm P. Atkinson; Maria E. Orlowska ; Patrick Valduriez; Stanley B. Zdonik; Michael L. Brodie (eds.). VLDB'99, Actas de la 25.ª Conferencia Internacional sobre Bases de Datos Muy Grandes, 7-10 de septiembre de 1999, Edimburgo, Escocia, Reino Unido . Morgan Kaufmann. págs. 278-289 . ISBN  978-1-55860-615-9.
  8. ↑ Wu K, Otoo E, Shoshani A (5 de marzo de 2004). "Sobre el rendimiento de los índices de mapa de bits para atributos de alta cardinalidad" (PDF) .
  9. ↑ Chambi, S.; Lemire, D.; Kaser, O.; Godin, R. (2016). "Mejor rendimiento de mapas de bits con mapas de bits Roaring". Software: Practice and Experience . 46 (5): 709– 719. arXiv : 1402.6407 . doi : 10.1002/spe.2325 . S2CID 1139669 . 
  10. ↑ Compresión de datos alineada por bytes
  11. ↑ Método de compresión de mapa de bits alineado con palabras, estructura de datos y aparato
  12. ↑ van Schaik, Sebastiaan; de Moor, Oege (2011). "Una estructura de datos de alcanzabilidad eficiente en memoria mediante compresión de vectores de bits" . Actas de la conferencia internacional de 2011 sobre gestión de datos . SIGMOD '11. Atenas, Grecia: ACM. pp. 913–924 . doi : 10.1145/1989323.1989419 . ISBN  978-1-4503-0661-4.
  13. 1 2 Deliège F, Pedersen TB (2010). "Lista de posiciones alineada por palabras híbrida: optimización del espacio y el rendimiento para mapas de bits comprimidos" (PDF) . En Ioana Manolescu, Stefano Spaccapietra, Jens Teubner, Masaru Kitsuregawa, Alain Leger, Felix Naumann, Anastasia Ailamaki, Fatma Ozcan (eds.). EDBT '10, Actas de la 13.ª Conferencia Internacional sobre la Extensión de la Tecnología de Bases de Datos . Nueva York, NY, EE. UU.: ACM. págs. 228–39 . doi : 10.1145/1739041.1739071 . ISBN  978-1-60558-945-9. S2CID 12234453 . Archivado del original (PDF) el 04-03-2011 . Recuperado el 02-02-2011 . 
  14. 1 2 F. Fusco; M. Stoecklin; M. Vlachos (septiembre de 2010). "NET-FLi: compresión, archivado e indexación sobre la marcha del tráfico de red en tiempo real" (PDF) . Proc. VLDB Endow . 3 ( 1–2 ): 1382–93 . doi : 10.14778/1920841.1921011 . S2CID 787443 . 
  15. 1 2 Lemire, D.; Kaser, O.; Aouiche, K. (2010). "La ordenación mejora los índices de mapas de bits alineados por palabras". Data & Knowledge Engineering . 69 : 3–28 . arXiv : 0901.3751 . doi : 10.1016/j.datak.2009.08.006 . S2CID 6297890 . 
  16. ↑ Conciso: Conjunto de enteros comprimidos y componibles. Archivado el 28 de mayo de 2011 en Wayback Machine .
  17. 1 2 Colantonio A, Di Pietro R (31 de julio de 2010). "Conciso: Conjunto de enteros componibles 'n' comprimidos" (PDF) . Information Processing Letters . 110 (16): 644– 50. arXiv : 1004.0403 . doi : 10.1016/j.ipl.2010.05.018 . S2CID 8092695. Archivado del original (PDF) el 22 de julio de 2011. Recuperado el 2 de febrero de 2011 . 
  18. ↑ Wu K, Otoo EJ, Shoshani A (2001). "Una comparación del rendimiento de los índices de mapas de bits" (PDF) . En Henrique Paques, Ling Liu , David Grossman (eds.). CIKM '01 Actas de la décima conferencia internacional sobre gestión de la información y el conocimiento . Nueva York, NY, EE. UU.: ACM. págs. 559–61 . doi : 10.1145/502585.502689 . ISBN  978-1-58113-436-0. S2CID 10974671 . Archivado del original (PDF) el 2011-07-20 . Recuperado el 2011-02-02 . 
  19. ↑ D. Lemire; O. Kaser; K. Aouiche (enero de 2010). "La ordenación mejora los índices de mapas de bits alineados por palabras". Data & Knowledge Engineering . 69 (1): 3– 28. arXiv : 0901.3751 . doi : 10.1016/j.datak.2009.08.006 . S2CID 6297890 . 
  20. 1 2 C.-Y. Chan; YE Ioannidis (1998). "Diseño y evaluación de índices de mapas de bits" (PDF) . En Ashutosh Tiwary; Michael Franklin (eds.). Actas de la conferencia internacional ACM SIGMOD de 1998 sobre gestión de datos (SIGMOD '98) . Nueva York, NY, EE. UU.: ACM. págs. 355–356 . doi : 10.1145/276304.276336 . ISBN  0897919955.
  21. ↑ C.-Y. Chan; YE Ioannidis (1999). "Un esquema de codificación de mapa de bits eficiente para consultas de selección" (PDF) . Actas de la conferencia internacional ACM SIGMOD de 1999 sobre gestión de datos (SIGMOD '99) . Nueva York, NY, EE. UU.: ACM. págs. 215-226 . doi : 10.1145/304182.304201 . ISBN  1581130848.
  22. ↑ PE O'Neil; D. Quass (1997). "Mejora del rendimiento de las consultas con índices variantes". En Joan M. Peckman; Sudha Ram; Michael Franklin (eds.). Actas de la conferencia internacional ACM SIGMOD de 1997 sobre gestión de datos (SIGMOD '97) . Nueva York, NY, EE. UU.: ACM. págs. 38–49 . doi : 10.1145/253260.253268 . ISBN  0897919114.
  23. ↑ N. Koudas (2000). «Indexación de mapas de bits con uso eficiente del espacio». Actas de la novena conferencia internacional sobre gestión de la información y el conocimiento (CIKM '00) . Nueva York, NY, EE. UU.: ACM. págs. 194–201 . doi : 10.1145/354756.354819 . ISBN  978-1581133202. S2CID 7504216 . 
  24. ↑ Spiegler I; Maayan R (1985). "Consideraciones sobre el almacenamiento y la recuperación de bases de datos binarias". Procesamiento y gestión de la información . 21 (3): 233– 54. doi : 10.1016/0306-4573(85)90108-6 .
  25. ↑ O'Neil, Patrick (1987). «Arquitectura y rendimiento del modelo 204». En Dieter Gawlick; Mark N. Haynie; Andreas Reuter (eds.). Actas del 2.º Taller Internacional sobre Sistemas de Transacciones de Alto Rendimiento . Londres, Reino Unido: Springer-Verlag. págs. 40–59 . 
  26. ↑ D. Rinfret; P. O'Neil; E. O'Neil (2001). "Aritmética de índices segmentados por bits". En Timos Sellis (ed.). Actas de la conferencia internacional ACM SIGMOD de 2001 sobre gestión de datos (SIGMOD '01) . Nueva York, NY, EE. UU.: ACM. págs. 47–57 . doi : 10.1145/375663.375669 . ISBN  1581133324.
  27. ↑ E. O'Neil; P. O'Neil; K. Wu (2007). "Opciones de diseño de índices de mapa de bits y sus implicaciones de rendimiento" (PDF) . 11.º Simposio Internacional de Ingeniería y Aplicaciones de Bases de Datos (IDEAS 2007) . págs. 72–84 . doi : 10.1109/IDEAS.2007.19 . ISBN  978-0-7695-2947-9. Archivado del original (PDF) el 20/07/2011 . Consultado el 02/02/2011 .
  28. ↑ "Clase BitArray (System.Collections)" . learn.microsoft.com . Consultado el 17 de diciembre de 2024 .
  29. ↑ Alex Bolenok (09-05-2009). "Creación de índices" .
  30. ↑ Egor Timoshenko. "Sobre colecciones mínimas de índices" (PDF) .
  31. ↑ Tom Lane (26-12-2005). "Re: Índices de mapa de bits, etc." . Listas de correo de PostgreSQL . Recuperado el 06-04-2007 .
Bibliografía
  • O'Connell, S. (2005). "Apuntes del curso de bases de datos avanzadas". Southampton : Universidad de Southampton .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  • O'Neil, P.; O'Neil, E. (2001). "Principios, programación y rendimiento de bases de datos". San Francisco : Morgan Kaufmann Publishers .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  • Zaker, M.; Phon-Amnuaisuk, S.; Haw, SC (2008). "Un diseño adecuado para grandes sistemas de almacenamiento de datos: índice de mapa de bits frente a índice de árbol B" (PDF) . Revista Internacional de Computadoras y Comunicaciones . 2 (2) . Recuperado el 7 de enero de 2010 .