Índice de mapa de bits

Ir a: navegación, búsqueda de

A Índice de mapa de bits es un especial tipo de Índice de base de datos que utiliza mapas de bits.

Los índices de mapa de bits se han considerado tradicionalmente a trabajar bien para columnas bajo-cardinalidad, que tienen un número modesto de valores distintos, absolutamente, o en relación con el número de registros que contienen los datos. El caso extremo de baja cardinalidad es datos Boolean (por ejemplo, un residente en una ciudad tiene acceso a internet?), que tiene dos valores True y False. Uso de índices de mapa de bits matrices de bits (comúnmente llamada mapas de bits) y responder a las consultas mediante la realización de operaciones lógicas bit a bit en estos mapas de bits. Índices de mapa de bits tienen una considerable ventaja de espacio y rendimiento sobre otras estructuras para consulta de dichos datos. Su inconveniente es que son menos eficientes que los tradicionales B-tree índices de columnas cuyos datos se actualización con frecuencia: por lo tanto, más a menudo se emplean en sistemas de sólo lectura que se especializan para consulta rápida - por ejemplo, los almacenes de datos, y generalmente no aptos para procesamiento de transacciones en línea aplicaciones.

Algunos investigadores sostienen que los índices de mapa de bits también son útiles para datos moderados o incluso alto-cardinalidad (por ejemplo, valores únicos datos) que se tiene acceso en modo sólo lectura, y acceder a consultas varias columnas indexadas de mapa de bits utilizando el AND, OR u operadores XOR extensivamente.[1]

También son útiles en los índices de mapa de bits almacenamiento de datos aplicaciones para unirse a una gran tabla de hechos a menor tablas de dimensiones tales como las dispuestas en una esquema en estrella.

Contenido

  • 1 Ejemplo
  • 2 Compresión
  • 3 Codificación
  • 4 Binning
  • 5 Historia
  • 6 Mapas de bits en memoria
  • 7 Referencias

Ejemplo

Continuando con el ejemplo de acceso a internet, un índice de mapa de bits puede lógicamente verse como sigue:

Identificador HasInternet Mapas de bits
Y N
1 Sí 1 0
2 No 0 1
3 No 0 1
4 No especificado 0 0
5 Sí 1 0

A la izquierda, Identificador se refiere al número único asignado a cada residente, HasInternet son los datos a ser indexado, se muestra el contenido del índice de mapa de bits como dos columnas bajo el título mapas de bits. Cada columna de la izquierda ilustración es un mapa de bits en el índice de mapa de bits. En este caso, hay dos dichos mapas de bits, uno para "internet" Sí y para "internet" No. Es fácil ver que cada uno un poco en mapa de bits Y indica si una fila determinada 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 valores más distintos. Por ejemplo, la cantidad de ventas es probable que un número mucho mayor de valores distintos. Las variaciones en el índice de mapa de bits pueden indizar eficazmente estos datos también. Repasamos brevemente tres variaciones.

Nota: muchas de las referencias citadas aquí son revisados en.[2] Para aquellos que puedan estar interesados en experimentar con algunas de las ideas mencionadas aquí, muchos de ellos se implementan en software de código abierto como FastBit,[3] El lémur de mapa de bits índice C++ Library,[4] la biblioteca de Java el rugir de mapa de bits,[5] el Colmena de Apache Sistema de almacén de datos y LucidDB.


Compresión

Software puede compresa cada mapa de bits en un índice de mapa de bits para ahorrar espacios. Ha habido una considerable cantidad de trabajo sobre este tema.[6][7] Normalmente emplean algoritmos de compresión de mapa de bits codificación de funcionamiento-longitud, como el código de mapa de bits bytes alineados,[8] el código Word-Aligned híbrido,[9] la compresión Partitioned Word-Aligned híbrido (PWAH),[10] la palabra lista posición alineada híbrido,[11] el índice de adaptación comprimido (COMPAX),[12] Mejorada alineado a la palabra híbrido (EWAH) [13] y la ' n ' comprimido entero componibles.[14][15] 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 sucinto pueden participar directamente en operaciones bit a bit sin descompresión. Esto les da ventajas considerables sobre técnicas de compresión genéricos tales como LZ77. Compresión de la BBC y sus derivados se utilizan en un comercial sistema de gestión de base de datos. BBC es efectivo en reducir el tamaño del índice y mantener consulta rendimiento. BBC codifica los mapas de bits en bytes, mientras que WAH codifica en palabras, mejor juego corriente CPU. "En tanto datos sintéticos y datos de la aplicación real, los nuevos esquemas de palabra alineado usan único de 50% más de espacio, pero realizan operaciones lógicas de datos comprimidos 12 veces más rápido que la BBC".[16] PLWAH mapas de bits se informaron que 50% de espacio de almacenaje consumido por WAH bitmaps y ofrecen hasta 20% de rendimiento más rápido en operaciones lógicas.[11] Consideraciones similares pueden hacerse para sucinto [15] y mejorada alineado a la palabra híbrido.[13]

El rendimiento de los esquemas como la BBC, WAH, PLWAH, EWAH, COMPAX y sucinto es dependiente del orden de las filas. Una simple especie lexicográfica puede dividir el tamaño del índice por 9 y hacer índices varias veces más rápido.[17] Cuanto mayor sea la tabla, el más importante es para ordenar las filas. Técnicas de reestructuración también se han propuesto para lograr los mismos resultados de la clasificación cuando se indexaba el streaming de datos.[12]

Codificación

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

Esto reduce el número de mapas de bits, más ahorro de espacio, pero para responder a cualquier consulta, la mayoría de los mapas de bits debe accederse. Esto hace que sea potencialmente no tan efectiva como la exploración una proyección vertical de la base de datos, también conocido como un vista materializada o índice de proyección. Encontrar el método de codificación óptima que equilibra el renidimiento de una consulta (arbitraria), mantenimiento de tamaño e Índice Índice sigue siendo un desafío.

Sin tener en cuenta la compresión, Chan y Ioannidis analizaron una clase de componentes múltiples métodos de codificación y llegó a la conclusión de que dos componentes de codificación se sienta en la torcedura del rendimiento vs curva índice tamaño y por lo tanto representa el mejor equilibrio entre rendimiento de tamaño y consulta de índice.[18]

Binning

Para las columnas alto-cardinalidad, es útil bin los valores, donde cada bin cubre varios valores y construir los mapas de bits para representar los valores de cada compartimiento. Este enfoque reduce el número de mapas de bits utilizados independientemente del método de codificación.[21] Sin embargo, los índices desechados sólo pueden responder algunas consultas sin examinar la base de datos. Por ejemplo, si una bandeja cubre el rango de 0.1 a 0.2, entonces cuando el usuario solicita todos los valores menos de 0.15, todas las filas que caen en la bandeja son posibles golpes y tienen que ser revisado para verificar si son en realidad menos de 0.15. El proceso de comprobación de la base de datos se conoce como candidato. En la mayoría de los casos, el tiempo utilizado por el cheque de candidato es significativamente mayor que el tiempo necesario para trabajar con el índice de mapa de bits. Por lo tanto, los índices desechados exhiben irregular rendimiento. Pueden ser muy rápidos para algunas consultas, pero mucho más lento si la consulta no coincide con un cubo.

Historia

El concepto de índice de mapa de bits se introdujo por el profesor Israel Spiegler y Rafi Maayan en su investigación "Almacenamiento y recuperación de las consideraciones de binario Bases de datos", publicado en 1985.[22] El primer producto comercial de base de datos para implementar un índice de mapa de bits fue Computer Corporation de Estados Unidos Modelo 204. Patrick O'Neil publicó un documento sobre esta implementación en 1987.[23] Esta implementación es un híbrido entre el índice básico de mapa de bits (sin compresión) y la lista de identificadores de fila (RID-lista). En general, el índice está organizado como un B + árbol. Cuando la cardinalidad de columna es baja, cada nodo hoja del árbol B contendría la larga lista de RID. En este caso, se requiere menos espacio para representar las RID-listas como mapas de bits. Puesto que cada mapa de bits representa un valor distinto, este es el índice básico de mapa de bits. A medida que aumenta la cardinalidad de columna, cada mapa de bits se vuelve escaso y puede tomar más espacio en disco para almacenar los mapas de bits que to almacenar el mismo contenido como listas de RID. En este caso, cambia para utilizar las listas de RID, que lo convierte en un B + árbol Índice.[24][25]

Mapas de bits en memoria

Una de las razones más fuertes para el uso de índices de mapa de bits es que los resultados intermedios producidos a partir de ellos también son mapas de bits y pueden ser reutilizados eficientemente en otras operaciones para responder a las consultas más complejas. Muchos lenguajes de programación este apoyan como estructura de datos de matriz un poco. Por ejemplo, Java tiene la BitSet clase.

Algunos sistemas de base de datos que no ofrecen los índices persistentes de mapa de bits usan mapas de bits internamente para acelerar el proceso de consulta. Por ejemplo, PostgreSQL las versiones 8.1 y posteriormente aplicación una "escaneo de índice de mapa de bits" optimización para acelerar hasta arbitrariamente complejo operaciones lógicas entre los índices disponibles en una sola tabla.

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

\mathbf{C}_n^\left [ \frac{n}{2} \right ] \equiv \frac{n!}{(n-\left [ \frac{n}{2} \right ])! \left [ \frac{n}{2} \right ]!}.[26] [27]

Un escaneo de índice de mapa de bits combina expresiones en diferentes índices, requiriendo solamente un índice por columna para apoyar todas las posibles consultas sobre una mesa.

Aplicar esta estrategia de acceso a índices B-tree también puede combinar consultas gama en varias columnas. En este enfoque, se crea un mapa de bits en memoria temporal con una bit para cada fila de la tabla (1 Lic. puede así almacenar entradas más 8 millones). A continuación, los resultados de cada índice se combinan en el mapa de bits utilizando operaciones bit a bit. Después se evalúan todas las condiciones, el mapa de bits contiene un "1" para las filas que coincidió con la expresión. Finalmente, el mapa de bits es atravesado y se recuperan filas coincidentes. Además de combinar eficientemente los índices, esto también mejora localidad de referencia de la tabla de accesos, porque todas las filas se obtienen secuencialmente en la tabla principal.[28] El mapa de bits interno se descarta después de la consulta. Si hay demasiadas filas en la tabla a utilizar 1 bit por fila, se crea un mapa de bits "con pérdida" en cambio, con un solo bit por página de disco. En este caso, el mapa de bits sólo se utiliza para determinar qué páginas a buscar; los criterios de filtro se aplican a todas las filas en la adecuación de páginas.

Referencias

Notas
  1. ^ ¿Índice Índice vs B-tree de mapa de bits: que y cuando?, Vivek Sharma, red técnica de Oracle.
  2. ^ John Wu (2007). "Anotadas referencias en el índice de mapa de bits".
  3. ^ FastBit
  4. ^ Lemur de mapa de bits índice C++ Library
  5. ^ El rugir de los mapas de bits
  6. ^ T. Johnson (1999). "Mediciones de rendimiento de los índices de mapa de bits comprimido". En Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie. Bases de VLDB 99, actas de la 25ª Conferencia Internacional sobre datos muy grandes, 7 – 10 de septiembre de 1999, Edimburgo, Escocia, Reino Unido. Morgan Kaufmann. PP. 278 – 89. ISBN1-55860-615-7.
  7. ^ Wu K, Otoo E, Shoshani un (05 de marzo de 2004). "Sobre el comportamiento de los índices de mapa de bits de atributos alta cardinalidad".
  8. ^ Compresión de datos byte alineado
  9. ^ Palabra alineados método de compresión de mapa de bits, estructura de datos y aparatos
  10. ^ van Schaik, Sebastiaan; de Moor, Oege (2011). "Actas del Congreso Internacional 2011 sobre gestión de datos". SIGMOD 11. Atenas, Grecia: ACM. págs. 913 – 924. Doi:10.1145/1989323.1989419. ISBN978-1-4503-0661-4. |Chapter = (ignoradoAyuda)
  11. ^ a b Deliège F, Pedersen TB (2010). "Palabra lista posición alineada híbrido: optimizar espacio y rendimiento para mapas de bits comprimidos". Ioana Manolescu, Stefano Spaccapietra, Jens Teubner, Masaru Kitsuregawa, Alain Léger, Felix Naumann, Anastasia Ailamaki y Fatma Ozcan. EDBT 10, procedimientos de la XIII Conferencia Internacional sobre la ampliación de la tecnología de base de datos. Nueva York, NY, USA: ACM. págs. 228 – 39. Doi:10.1145/1739041.1739071. ISBN978-1-60558-945-9.
  12. ^ a b F el. Fusco, M. Stoecklin, M. Vlachos (septiembre de 2010). "NET-FLi: compresión on-the-fly, archivar e indexación de tráfico de red en streaming". Proc. VLDB dotar 3 (1 – 2): 1382 – 93.
  13. ^ a b Lemire, D.; Kaser, O.; Aouiche, K. (2010). "Clasificación mejora los índices de mapa de bits alineado a la palabra". Datos & Ingeniería del conocimiento 69:: 3. Doi:10.1016/j.datak.2009.08.006. editar
  14. ^ Conciso: Comprimido ' n ' Set entero componibles
  15. ^ a b Colantonio A, Di Pietro R (31 de julio de 2010). "Sucinto: comprimido ' n ' componentes Integer Set". Letras de procesamiento de información 110 (16): 644 – 50. Doi:10.1016/j.IPL.2010.05.018.
  16. ^ Wu K, Otoo EJ, Shoshani A (2001). "Una comparación del desempeño de los índices de mapa de bits". Henrique Paques, Ling Liu y David Grossman. CIKM ' 01 actas de la décima Conferencia Internacional sobre gestión de información y conocimiento. Nueva York, NY, USA: ACM. 559 págs. – 61. Doi:10.1145/502585.502689. ISBN1-58113-436-3.
  17. ^ D. Lemire, Kaser o., K. Aouiche (enero de 2010). "Clasificación mejora los índices de mapa de bits alineado a la palabra". Datos & Ingeniería del conocimiento 69 (1): 3 – 28. arXiv:0901.3751. Doi:10.1016/j.datak.2009.08.006.
  18. ^ a b C.-Y. Chan y Y. E. Ioannidis (1998). "Diseño de mapa de bits índice y evaluación". En Ashutosh Behroozi, Michael Franklin. Actas de la Conferencia Internacional ACM SIGMOD 1998 gestión de datos (SIGMOD 98). Nueva York, NY, USA: ACM. págs. 355 – 6. Doi:10.1145/276304.276336.
  19. ^ C.-Y. Chan y Y. E. Ioannidis (1999). "Un mapa de bits eficiente esquema de codificación para las consultas de selección". Actas de la Conferencia Internacional ACM SIGMOD 1999 gestión de datos (SIGMOD 99). Nueva York, NY, USA: ACM. págs. 215 – 26. Doi:10.1145/304182.304201.
  20. ^ P. E. o ' Neil y Quass D. (1997). Joan M. Peckman, Sudha Ram, Michael Franklin, ed. "actas de la Conferencia Internacional ACM SIGMOD 1997 gestión de datos (SIGMOD 97)". Nueva York, NY, USA: ACM. págs. 38 a 49. Doi:10.1145/253260.253268. |Chapter = (ignoradoAyuda)
  21. ^ N. Koudas (2000). "Espacio de indexación eficiente de mapa de bits". Actas de la novena Conferencia Internacional sobre gestión de la información y el conocimiento (CIKM ' 00). Nueva York, NY, USA: ACM. PP. 194 – 201. Doi:10.1145/354756.354819.
  22. ^ Spiegler; Maayan R (1985). "Consideraciones de almacenamiento y recuperación de bases de datos binarios". Gestión y procesamiento de la información: una publicación internacional 21 (3): 233 – 54. Doi:10.1016/0306-4573 (85) 90108-6.
  23. ^ O ' Neil, Patrick (1987). Dieter Gawlick, Mark N. Haynie y Andreas Reuter (eds.), ed. "Actas del 2do taller internacional sobre sistemas de transacciones de alto rendimiento". Londres, Reino Unido: Springer-Verlag. págs. 40 a 59. |Chapter = (ignoradoAyuda)
  24. ^ D. Rinfret, P. O'Neil y E. o ' Neil (2001). Timos Sellis (Ed.), ed. "Actas de la Conferencia Internacional ACM SIGMOD 2001 gestión de datos (SIGMOD ' 01)". Nueva York, NY, USA: ACM. págs. 47-57. Doi:10.1145/375663.375669. |Chapter = (ignoradoAyuda)
  25. ^ E. o ' Neil, P. o ' Neil, K. Wu (2007). "11 de base de datos internacional de ingeniería y aplicaciones Simposio (IDEAS 2007)". págs. 72-84. Doi:10.1109/IDEAS.2007.19. ISBN0-7695-2947-X. |Chapter = (ignoradoAyuda)
  26. ^ Alex Bolenok (2009-05-09). "Creación de índices".
  27. ^ Egor Timoshenko. "El mínimas colecciones de índices".
  28. ^ Tom Lane (2005-12-26). "Re: mapa de bits, índices etc..". Listas de correo de PostgreSQL. 2007-04-06.
Bibliografía
  • O ' Connell, S. (2005). "Avanzados" notas del curso de bases de datos. Southampton: Universidad de Southampton
  • O ' Neil, P.; O ' Neil, E. (2001). "Principios de base de datos, programación y rendimiento". San Francisco: Morgan Kaufmann Publishers
  • Zaker que, M.; Phon-Amnuaisuk, S.; Haw, S.C. (2008). "Un diseño adecuado para grandes sistemas de almacenamiento de datos: índice de mapas de bits versus índice B-tree". Revista Internacional de informática y comunicaciones 2 (2). 2010-01-07

Otras Páginas

Obtenido de"https://en.copro.org/w/index.php?title=Bitmap_index&oldid=629779177"