performance - profundidad - recorrido de arboles
Árboles b vs árboles binarios (2)
La complejidad algorítmica es la misma, ya que O (log b n) = O (c log n) = O (log n) pero los factores constantes son muy diferentes.
Los árboles B se diseñaron para discos duros de discos, que tienen un gran tiempo de acceso (mover la cabeza a su posición) después de lo cual se lee un sector físico completo. Al hacer que los nodos del árbol B sean tan grandes como el sector, se minimiza el número de tiempos de acceso y se maximizan los datos útiles de cada operación de lectura.
Pero si está trabajando fuera de la memoria (o SSD) tiene un tiempo de acceso insignificante, por lo tanto, una mejor comparación es contar el número de palabras individuales a las que accedió.
Por ejemplo, planifiquemos una estructura de datos para almacenar 2 20 claves de 1 palabra cada una, para un total de 4MiB de datos sin procesar en una máquina de 32 bits.
Un B-tree "fornido", hecho para discos duros contemporáneos, tendrá nodos 4kiB, que pueden contener hasta 512 teclas y punteros (más o menos). Una profundidad de 2 con un 100% de relleno contiene 2 18 claves, por lo que necesitamos una profundidad de 3. ¿Cuál será el aspecto promedio de la búsqueda? En promedio, tendrá que leer 3/8 (la mitad del relleno promedio 3/4) de cada nodo en su ruta, desde la raíz hasta el final = 4608 palabras .
Un árbol de búsqueda binario tendrá 2 20 nodos, cada uno con una clave y dos punteros (3 palabras). La profundidad será 20. La búsqueda promedio tendrá que leer la clave y uno de los indicadores de cada nodo en su ruta, desde la raíz hasta el final = 40 palabras .
El almacenamiento en memoria caché posiblemente puede aliviar la diferencia, pero no puede revertir estos números.
Por otro lado, los árboles B de solo memoria con un factor de ramificación mucho más limitado parecen funcionar mejor que los árboles binarios en la práctica .
32 teclas por nodo en particular parece ser un punto dulce para las arquitecturas actuales, tanto de 32 como de 64 bits. Muchos lenguajes y bibliotecas más nuevos utilizan árboles B de 32 teclas como una estructura de datos integrada, junto con tablas hash y matrices o como un reemplazo para ellos. Este uso fue encabezado por Clojure y otros lenguajes funcionales, pero posteriormente fue utilizado por lenguajes más comunes como Javascript, con el reciente enfoque en estructuras de datos inmutables (por ejemplo, Immutable.js )
Este resultado puede deberse al hecho de que, aunque las palabras a las que accede un algoritmo de árbol B son más que las de un árbol binario, la cantidad de caché falla (las operaciones de lectura que hacen que la CPU se detenga y esperen la RAM principal) puede ser más bajo que en un árbol binario, si la arquitectura de almacenamiento en caché puede obtener trozos de RAM que contienen un nodo de árbol B completo a la vez.
Aquí estamos de nuevo, la optimización es la misma que para el almacenamiento masivo basado en disco, donde usamos árboles B con nodos tan grandes como el sector físico, para minimizar los tiempos de acceso. En este caso, utilizamos un árbol B con nodos tan grandes como la operación de lectura que realiza el caché de Nivel 3 en la RAM, para minimizar las fallas de caché.
Si estoy implementando la operación de búsqueda en memoria (RAM) con b árboles, ¿sería mejor en términos de almacenamiento en caché o algunos otros efectos en comparación con los árboles binarios?
Lo que sé es
binary search tress---O(log n)
btrees ---------------O(c log n)
Hubo mucha discusión al respecto en varios blogs.
Los árboles B se diferencian de los árboles binarios en que las claves y los punteros se agrupan en la memoria, por lo que se obtiene un comportamiento de caché algo mejor tanto en el disco como en la memoria. Sin embargo, no hay diferencia en el tiempo de ejecución asintótico (big-O).