Universidad Politécnica de Honduras
Ing. Welbyn J. Espinal
Organizaciones Indexadas
1. ¿Para qué son útiles las Organizaciones Indexadas?
Las organizaciones indexadas son útiles para mejorar la eficiencia en el acceso a través de claves de búsqueda en el almacenamiento auxiliar en forma de índices. Con esta práctica, se habrá de implementar al menos un índice, y tantos como se estime oportuno.
2. ¿De qué consta cada entrada y qué son los índices?
Los índices son archivos que se componen de entradas. Cada entrada consta de:
- Entrada de datos: valor de la clave de indización para esa entrada.
- Referencia al registro: puntero, que puede ser físico o lógico, según el caso.
3. ¿Cómo se clasifican los índices?
Podemos clasificar los índices en dos tipos principales:
- Primarios: las claves de las entradas tienen valores únicos.
- Secundarios: la clave de indexación tendrá valores repetidos, y será necesario contemplar esto en las operaciones del índice.
4. ¿Cuáles son las operaciones básicas de la indexación y cómo funcionan?
- a. Crear índice: recibe la clave de indización (campos a indexar) y construye el índice. Si el campo ya estuviera indexado, la operación se abortaría, ya que no deberíamos tener el mismo índice sobre una misma clave.
- b. Borrar índice: borra el índice (destruye el archivo).
Ordenamiento de Archivos
5. ¿Qué implica el Ordenamiento de Archivos?
Implica una mejora de la eficiencia en la búsqueda de los archivos.
6. ¿Cuáles son las técnicas básicas de Ordenamiento?
Ordenamientos internos y Ordenamientos externos.
7. ¿Cuándo se aplica el ordenamiento interno?
Se aplican cuando el conjunto de datos a clasificar es lo suficientemente pequeño, de tal forma que pueda caber en la memoria principal.
8. Son métodos de Ordenamiento interno
- Ordenamiento por Burbuja
- Ordenamiento por Inserción
- Ordenamiento por Selección
- Ordenamiento por MergeSort
- Ordenamiento por QuickSort
- Ordenamiento por HeapSort
9. ¿En qué consiste el ordenamiento por burbuja?
En comparar pares de valores de llaves e intercambiarlos si no están en sus posiciones relativas correctas.
10. ¿En qué consiste el ordenamiento por inserción?
Es básicamente tomar la siguiente llave de una lista no clasificada e insertarla en su posición relativa correspondiente en una lista creciente de datos clasificados.
11. ¿En qué consiste el ordenamiento por MergeSort?
Consiste en tomar la lista de llaves, dividirla en dos partes y ordenarlas en forma independiente.
12. ¿En qué consiste el ordenamiento por QuickSort?
Consiste en escoger una llave aleatoriamente como referencia y se ordena a partir de esta llave. En el peor de los casos, la llave aleatoria seleccionada que sería la del extremo, QuickSort funciona correctamente.
13. ¿En qué consiste el ordenamiento por HeapSort?
Se comporta mejor en los peores casos y se basa en el uso de un árbol binario llamado apilamiento.
Organizaciones Basadas en Árboles
14. ¿Qué es un Árbol en Informática?
Un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él.
15. ¿Cuáles son los tipos de Árboles?
- Árboles Binarios
- Árbol de búsqueda binario auto-balanceable
- Árboles B
- Árboles Multicamino
16. ¿Qué es un Árbol binario?
Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre «binario»).
17. ¿Qué es un árbol binario auto-balanceable?
Un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente.
18. ¿Qué son los Árboles B?
Son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles B representan una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo. Varían en Árbol B+ y Árbol B*.
19. ¿Qué es un Árbol B+?
Un árbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste respecto a un árbol-B, toda la información se guarda en las hojas.
20. ¿Qué es un Árbol B*?
Es una variante de Árbol-B que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2.
Transformación de Claves (Hashing)
21. ¿Qué significa la Transformación de Claves (Hashing)?
Es un método que permite aumentar la velocidad de búsqueda sin necesidad de tener los elementos ordenados. Trabaja basándose en una función de transformación o función hash (h) que convierte una clave dada en una dirección (índice) dentro del arreglo.
22. ¿Qué debe hacer la función hash (h)?
La función hash debe generar posiciones diferentes dadas dos claves diferentes. Si esto no ocurre, hay una colisión.
23. ¿Qué es una colisión?
Una colisión se define como la asignación de una misma dirección a dos o más claves distintas.
24. ¿Cuáles son los métodos para resolver colisiones?
- Reasignación
- Arreglos Anidados
- Encadenamiento
25. ¿Qué es un bucket (compartimiento) y cuáles son sus ventajas?
Es un bloque de registros que se extraen en un acceso a disco cuando comparten la misma dirección. Sus ventajas son:
- Minimiza el número de colisiones.
- Minimiza el tiempo de acceso a las claves y el espacio utilizado en el almacenamiento.
- El tamaño de la tabla Hash es menor.