Diccionarios en memoria externa
Jérémy Barbay 31 Ago 201031/08/10 a las 15:16 hrs.2010-08-31 15:16:31
2.4 Diccionarios en memoria externa
===========================
Author: Jérémy Barbay
Date: 2010-08-31 19:14:57 XXX
1. B-arbol
1) (2,3) Arbol: un arbol de busqueda donde
- cada nodo tiene 1 o 2 llaves, que corresponde a 2 o 3
hijos, con la excepcion de la raiz;
- todas las hojas son al mismo nivel (arbol completamente balanceado)
- Propiedades:
- altura de un (2,3) arbol?
- tiempo de busqueda?
- insercion en un (2,3) arbol?
- delecion en un (2,3) arbol?
2) (d,2d) Arbol un arbol donde
- cada nodo tiene de d a 2d hijos, con la excepcion de la
raiz (significa d-1 a 2d-1 llaves).
- todas las hojas son al mismo nivel (arbol completamente
balanceado)
- Propiedades:
- altura de un (d,2d) arbol?
- tiempo de busqueda?
- insercion en un (d,2d) arbol?
- delecion en un (d,2d) arbol?
3) B-Arbol, y variantes
- B-Arbol
- [
- [en.wikipedia.org/wiki/B-tree]
- B^* arbol
- non-root nodes to be at least 2/3 full instead of 1/2
- [en.wikipedia.org/wiki/B*-tree]
- B^+ arbol
- the leaf nodes of the tree are chained together in the form of a linked list.
- [
2. Van Emde Boas arbol (vEB)
[en.wikipedia.org/wiki/Van_Emde_Boas_tree]
1) Historia:
- Originalemente (1977) un estructura de datos normal, que
suporta todas las operaciones en $O(\llg n) = O(\lg \lg
n)$, inventada por el equipo de Peter van Emde Boas.
- No considerado utiles en practica para "pequeños"
arboles.
- Applicacion a "Cache-Oblivious" algoritmos y estructuras de datos
- optimiza el cache sin conocer el tamaño B de sus paginas
- => optimiza todos los niveles sin conocer B_1,...,B_k
- otras applicaciones despues en calculo parallelo (?)
2) Definicion
- Cada nodo contiene un arbol van EmdeBoas sobre $\sqrt{n}$ elementos
- \llg n niveles de arboles
- operadores:
* Findnext
* Insert
* Delete
3) Analisis
- Busqueda en "tiempo" O(\lg n / \lg B) a cualquier nivel
$i$, donde el tiempo es la cuantidad de accessos al cache
del nivel considerado
- Insercion
- Delecion
3. Finger Search Tree: la busqueda doblada de los arboles de busqueda
1) Estructura de datos
2) algorimo de busqueda
3) analisis: busqueda en O(\lg p)
===========================
Author: Jérémy Barbay
Date: 2010-08-31 19:14:57 XXX
1. B-arbol
1) (2,3) Arbol: un arbol de busqueda donde
- cada nodo tiene 1 o 2 llaves, que corresponde a 2 o 3
hijos, con la excepcion de la raiz;
- todas las hojas son al mismo nivel (arbol completamente balanceado)
- Propiedades:
- altura de un (2,3) arbol?
- tiempo de busqueda?
- insercion en un (2,3) arbol?
- delecion en un (2,3) arbol?
2) (d,2d) Arbol un arbol donde
- cada nodo tiene de d a 2d hijos, con la excepcion de la
raiz (significa d-1 a 2d-1 llaves).
- todas las hojas son al mismo nivel (arbol completamente
balanceado)
- Propiedades:
- altura de un (d,2d) arbol?
- tiempo de busqueda?
- insercion en un (d,2d) arbol?
- delecion en un (d,2d) arbol?
3) B-Arbol, y variantes
- B-Arbol
- [
- [en.wikipedia.org/wiki/B-tree]
- B^* arbol
- non-root nodes to be at least 2/3 full instead of 1/2
- [en.wikipedia.org/wiki/B*-tree]
- B^+ arbol
- the leaf nodes of the tree are chained together in the form of a linked list.
- [
2. Van Emde Boas arbol (vEB)
[en.wikipedia.org/wiki/Van_Emde_Boas_tree]
1) Historia:
- Originalemente (1977) un estructura de datos normal, que
suporta todas las operaciones en $O(\llg n) = O(\lg \lg
n)$, inventada por el equipo de Peter van Emde Boas.
- No considerado utiles en practica para "pequeños"
arboles.
- Applicacion a "Cache-Oblivious" algoritmos y estructuras de datos
- optimiza el cache sin conocer el tamaño B de sus paginas
- => optimiza todos los niveles sin conocer B_1,...,B_k
- otras applicaciones despues en calculo parallelo (?)
2) Definicion
- Cada nodo contiene un arbol van EmdeBoas sobre $\sqrt{n}$ elementos
- \llg n niveles de arboles
- operadores:
* Findnext
* Insert
* Delete
3) Analisis
- Busqueda en "tiempo" O(\lg n / \lg B) a cualquier nivel
$i$, donde el tiempo es la cuantidad de accessos al cache
del nivel considerado
- Insercion
- Delecion
3. Finger Search Tree: la busqueda doblada de los arboles de busqueda
1) Estructura de datos
2) algorimo de busqueda
3) analisis: busqueda en O(\lg p)
| Compartir | |
|---|---|
| Última Modificación | 31 Ago 201031/08/10 a las 15:16 hrs.2010-08-31 15:16:31 |
| Vistas Únicas | 1 |
| Comentarios |
|
