Berkeleydb - B-Tree versus Hash Table

Question

Estoy tratando de comprender qué debería impulsar la elección del método de acceso al usar un BerkeleyDB: B-Tree versus HashTable. Una tabla Hash proporciona O (1) búsqueda pero las inserciones son costosas (utilizando hashing lineal/extensible obtenemos amortización O (1) para insertar). Pero los B-Trees proporcionan tiempos de búsqueda e inserción de log N (base B). Un B-Tree también puede admitir consultas de rango y permitir el acceso en orden ordenado.

1. Aparte de estas consideraciones, ¿qué más se debe tener en cuenta?
2. Si no necesito admitir consultas de rango, ¿puedo usar un método de acceso Hashtable?

Answer 1

Depende de su conjunto de datos y claves En pequeños conjuntos de datos su punto de referencia será similar, sin embargo en conjuntos de datos más grandes puede variar dependiendo del tipo de claves/la cantidad de datos que tenga. Por lo general, b-tree es mejor, hasta que los metadatos btree excedan tu caché y termine haciendo mucho io, en ese caso el hash es mejor. Además, como señaló, los insertos de b-tree son más caros, si encuentra que va a hacer muchas inserciones y pocas lecturas, hash puede ser mejor, si encuentra que hace pequeños insertos, pero muchas lecturas, b-tree puede se mejor

Si está realmente preocupado por el rendimiento que podría intentar ambos métodos y ejecutar sus propios puntos de referencia =]

Answer 2

Cuando los conjuntos de datos se ponen muy grandes, los árboles B son aún mejor, porque la mayoría de los metadatos internos pueden todavía encajar en el caché. Los hashes, por su naturaleza (distribución aleatoria uniforme de datos) son intrínsecamente caóticos. Es decir, una vez que el tamaño total del conjunto de datos excede el tamaño de la memoria de trabajo, el rendimiento del hash desciende de un acantilado mientras que el rendimiento del árbol B se degrada graciosamente (en realidad, de forma logarítmica).

Answer 3

Para citar los dos autores principales de Berkeley DB en this escritura de la arquitectura:

La principal diferencia entre Btree y métodos de acceso Hash es que Btree ofrece la localidad de referencia para las llaves, mientras Hash hace no. Esto implica que Btree es el método de acceso correcto para casi todos los conjuntos de datos ; sin embargo, el método de acceso Hash es apropiado para conjuntos de datos tan grande que ni siquiera las estructuras de indexación de Btree caben en la memoria. En ese punto, es mejor usar la memoria para datos que para indexar las estructuras . Esta compensación tuvo mucho más sentido en 1990 cuando la memoria principal era típicamente mucho más pequeña que hoy.

Por lo tanto, quizás en los dispositivos integrados y casos de uso especializado, una tabla hash puede funcionar. BTree se utiliza en sistemas de archivos modernos como Btrfs y es prácticamente la estructura de datos de la idea para construir bases de datos o sistemas de archivos.

Answer 4

Para muchas aplicaciones, se accede a una base de datos al azar, interactivamente o con "transacciones". Esto podría suceder si tiene datos entrantes en desde un servidor web. Sin embargo, a menudo debe llenar una gran base de datos de una sola vez, como una operación "por lotes". Esto podría suceder si está realizando un proyecto de análisis de datos o está migrando una base de datos anterior a un formato nuevo .

Cuando está completando una base de datos a la vez, un árbol B u otro índice clasificada es preferible, ya que permite que las inserciones de lote a hacerse mucho más eficiente.Esto se logra ordenando las claves antes de ponerlas en la base de datos. Llenar una base de datos BerkeleyDB con 10 millones de entradas puede tardar una hora cuando las entradas no están ordenadas, porque cada acceso es una falta de caché. Pero cuando se clasifican las entradas , el mismo procedimiento puede tomar solo diez minutos. La proximidad de claves consecutivas significa que utilizará varios cachés para casi todas las inserciones. La ordenación se puede hacer muy rápidamente, de modo que toda la operación se puede acelerar multiplicando ordenando los datos antes de insertarlos. Con la indexación de hashtable, porque no sabe de antemano qué teclas terminarán al lado de cada otra, esta optimización no es posible.

Actualización: decidí proporcionar un ejemplo real. Se basa en la siguiente secuencia de comandos "db-test"

#!/usr/bin/perl 
use warnings; 
use strict; 
use BerkeleyDB; 
my %hash; 
unlink "test.db"; 
tie %hash, (shift), -Filename=>"test.db", -Flags=>DB_CREATE or die; 
while(<>) { $hash{$_}=1; } 
untie %hash; 

podemos probar con un archivo de índice Wikipedia volcado de 16 millones de entradas. (Me estoy quedando esto en un ordenador portátil de 800 MHz de 2 núcleos, con 3G de la memoria)

$ >enw.tab bunzip2 <enwiki-20151102-pages-articles-multistream-index.txt.bz2 
$ wc -l enw.tab 
16050432 enw.tab 
$ du -shL enw.tab 
698M enw.tab 
$ time shuf enw.tab > test-shuf 
    16.05s user 6.65s system 67% cpu 33.604 total 
$ time sort enw.tab > test-sort 
    70.99s user 10.77s system 114% cpu 1:11.47 total 
$ time ./db-test BerkeleyDB::Btree < test-shuf 
    682.75s user 368.58s system 42% cpu 40:57.92 total 
$ du -sh test.db 
1.3G test.db 
$ time ./db-test BerkeleyDB::Btree < test-sort 
    378.10s user 10.55s system 91% cpu 7:03.34 total 
$ du -sh test.db 
923M test.db 
$ time ./db-test BerkeleyDB::Hash < test-shuf 
    672.21s user 387.18s system 39% cpu 44:11.73 total 
$ du -sh test.db 
1.1G test.db 
$ time ./db-test BerkeleyDB::Hash < test-sort 
    665.94s user 376.65s system 36% cpu 46:58.66 total 
$ du -sh test.db 
1.1G test.db 

se puede ver que la preclasificación de las teclas BTree deja caer el tiempo de inserción por debajo de 41 minutos a 7 minutos. La ordenación demora solo 1 minuto, por lo que hay una gran ganancia neta: la creación de la base de datos es 5 veces más rápida. Con el formato Hash, los tiempos de creación son igualmente lentos si la entrada está ordenada o no. También tenga en cuenta que el tamaño del archivo de la base de datos es más pequeño para las inserciones clasificadas; presumiblemente esto tiene que ver con el equilibrio de los árboles.

La aceleración debe ser debido a algún tipo de almacenamiento en caché, pero no estoy seguro de donde. Es probable que tengamos menos errores de caché en la memoria caché de la página del kernel con inserciones ordenadas. Esto sería coherente con los números de uso de CPU : cuando hay una caché de página falta, el proceso tiene que esperar mientras la página se recupera del disco, por lo que el uso de la CPU es inferior.

También realicé las mismas pruebas con dos archivos más pequeños, para comparar.

File  | WP index   | Wikt. words  | /usr/share/dict/words 
Entries | 16e6    | 4.7e6    | 1.2e5 
Size  | 700M    | 65M    | 1.1M 
shuf time | 34s    | 4s    | 0.06s 
sort time | 1:10s   | 6s    | 0.12s 
------------------------------------------------------------------------- 
      | total DB CPU |     | 
      | time size usage|     | 
------------------------------------------------------------------------- 
Btree shuf | 41m, 1.3G, 42% | 5:00s, 180M, 88% | 6.4s, 3.9M, 86% 
     sort | 7m, 920M, 91% | 1:50s, 120M, 99% | 2.9s, 2.6M, 97% 
Hash shuf | 44m, 1.1G, 39% | 5:30s, 129M, 87% | 6.2s, 2.4M, 98% 
     sort | 47m, 1.1G, 36% | 5:30s, 129M, 86% | 6.2s, 2.4M, 94% 
------------------------------------------------------------------------- 
Speedup | 5x    | 2.7x    | 2.2x 

Con el conjunto de datos más grande, las inserciones clasificadas nos dan una velocidad 5 veces mayor. Con el más pequeño, seguimos obteniendo una aceleración de 2x, aunque los datos se ajustan fácilmente a la memoria, por lo que el uso de la CPU siempre es alto. Esto parece para implicar que nos estamos beneficiando de otra fuente de eficiencia en además de la memoria caché de página, y que la aceleración 5x en realidad era debido en partes iguales a la memoria caché de página y algo más - ¿quizás el mejor balanceo de árboles ?

En cualquier caso, tiendo a preferir el formato Btree porque permite operaciones por lotes más rápidas. Incluso si se accede a la base de datos final al al azar, utilizo las operaciones por lotes para el desarrollo, las pruebas y el mantenimiento . La vida es más fácil si puedo encontrar una forma de acelerar esto.