1

Sistemas de almacenamiento de la información

Objetivos del capítulo

4 Aprender qué son y cómo se utilizan los archivos secuenciales, aleatorios e indexados. 4 Entenderlos en un contexto de evolución histórica. 4 Conocer sus ventajas e inconvenientes. 4 Entender en qué manera han influido en el posterior diseño de las bases de datos relacionales.

GESTIÓN DE BASES DE DATOS

1.1

© RA-MA

sistema basado en archivos

1.1.1 Historia de los archivos Debemos entender la evolución de las bases de datos como un proceso continuo de modernización que nos ha llevado desde el papel hasta el estado actual. Hace treinta años, las necesidades eran menores y los grandes ordenadores enfocaban sus objetivos a controlar los procesos básicos de una empresa, que en aquel momento eran la contabilidad en primer término y tras ello la facturación. Hoy día controlamos muchas más cosas; los procesos de la producción; la optimización de los recursos; los documentos de la empresa; los centros de comunicación con el cliente; la inteligencia de negocio aplicada a las ventas y tantos otros. En cambio, hace treinta años, los problemas se podían solucionar con una decena de archivos, ¿Quién me quiere comprar algo? Mis clientes. Por tanto necesito un archivo de clientes. ¿Quién me suministra la materia prima? Mis proveedores. Por tanto necesitamos un archivo de proveedores. Y así sucesivamente. La mayor parte de las empresas de hace treinta años utilizaban archivos de papel, donde anotaban los datos de sus clientes en forma de fichas escritas con una máquina de escribir de la época. Por eso los archivos también recibían el nombre de ficheros, y por esa razón también la primera informatización empezaba por pasar del sistema de fichas de papel o de cartulina a un sistema informatizado. La principal ventaja del sistema informatizado estaba en evitar tiempo para encontrar una ficha de papel dentro de un enorme cajón de fichas. Poder encontrar una ficha en menos de un minuto ya era una importante diferencia con respecto a enviar a una persona a buscarla a otra planta del edificio (el archivo de muchas empresas solía estar en los sótanos) y traérnosla al cabo de cinco minutos. Pasábamos, pues, de un sistema en que el soporte era papel, a un nuevo sistema en el que el soporte era digital.

20

© RA-MA

1

n

SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIÓN

1.1.2 Métodos de acceso a los datos Toda la historia de los archivos ha ido ligada al avance de la tecnología; principalmente del hardware y en menor medida del software. A continuación vamos a ver cuatro tipos de archivos, aunque los más utilizados han sido tres: 1 2 3 4

Archivos secuenciales. Archivos de acceso aleatorio. Archivos indexados. Archivos hash.

Los archivos de los tipos 1, 2 y 3 son los más comunes, puesto que cuando se empezaron a utilizar los archivos hash, el concepto de base de datos cambió y se cuestionó también el complejo sistema hash frente a sus mejoras de rendimiento. Veamos con detalle estos tipos de acceso a los archivos.

1.2

Archivos secuenciales

Situémonos en la época. Los sistemas de almacenamiento físico eran tambores de cinta magnética de un diámetro comparable al de los antiguos discos de vinilo conocidos como LP. En casa es posible que nuestros padres tengan aún unas cintas de música llamadas cassettes. Pues bien, las unidades de cinta informáticas eran como unos cassettes gigantes donde se almacenaban datos digitales: ceros y unos en orden secuencial.

21

GESTIÓN DE BASES DE DATOS

© RA-MA

¿Qué quiere decir secuencial? Que van ordenados en posiciones sucesivas, y que si queremos llegar a la posición número 100, debemos pasar antes por la 1, la 2 y así sucesivamente; secuencialmente. Este era el hardware que teníamos y el software de gestión más sencillo era el procesador de textos. No pensemos en un procesador de textos como Word. Word es una maravilla comparado con lo que había en la época. No había tipos de letra. No podíamos ver cómo quedaba el formato del documento. Teníamos editores de líneas; es decir, disponíamos de instrucciones para abrir un archivo concreto quedándonos en la línea cero por defecto; otros comandos para desplazarnos hasta una línea, mostrar su contenido; modificar a partir de una posición y almacenar los cambios línea a línea. Tras ello, con otro comando grabábamos el archivo y finalmente con el comando Q salíamos de nuevo a la pantalla negra del sistema operativo. El sistema más normal para crear un archivo de clientes era escribir su nombre, separar con un retorno de carro, escribir su dirección seguida de otro retorno de carro, población y así sucesivamente. Entre cliente y cliente se colocaba una marca de final de bloque que indicaba el inicio de los datos de un nuevo cliente o bien el final del archivo de clientes. Cada uno de estos bloques con los datos de un cliente recibe el nombre de registro y cada una de estas informaciones (nombre, dirección, población, etc.) recibe el nombre de campo. Por tanto, un registro se compone de campos. Veamos un ejemplo: Juan Martínez Calle del Pez, 5 Madrid Comercial Martínez Calle de la Cuesta, 10 Sevilla José Sánchez Calle Mayor, 7 Salamanca

22

© RA-MA

1

n

SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIÓN

1.2.1 Utilidad de los archivos secuenciales para imprimir Este tipo de archivos era muy útil si tenía justamente este formato, puesto que servía para imprimir etiquetas y enviar circulares. La marca que también podía sustituirse por un punto solitario, quedaba en el espacio entre etiquetas y no se veía. Esto funcionaba siempre que tuviésemos el cuidado de colocar bien el cabezal de la impresora en la primera etiqueta. Si no, teníamos que abortar el listado porque las etiquetas salían desplazadas. Y a repetir de nuevo. ¿Qué era el cabezal de la impresora? Sólo teníamos impresoras de agujas. Las láser tardaron más tiempo en salir al mercado y su precio era prohibitivo para la mayor parte de empresas; ¡sólo las compraban las imprentas! Las impresoras de agujas disponían de un cabezal con una matriz de filas de 9 agujas que golpeaban una cinta empapada en tinta, dejando la huella del impacto sobre el papel o en este caso sobre la etiqueta.

23

GESTIÓN DE BASES DE DATOS

© RA-MA

Pues bien, este era el sistema de trabajo con un archivo de clientes, y en la primera época eran sólo los informáticos (con bata blanca) los autorizados a trabajar con los editores de líneas para confeccionar los archivos de clientes. Imprimir las etiquetas para enviar las cartas era un trabajo que, si se hacía a máquina, podría tardar semanas. Con el ordenador y la impresora se podía hacer en media hora.

1.2.2 Características de los archivos secuenciales

1.2.2.1 Lectura ordenada obligatoria Para leer un registro situado en medio del archivo debemos pasar por todos los registros anteriores.

1.2.2.2 No permite el retroceso (forward only) En los archivos secuenciales se realiza la lectura sólo hacia delante. Por ejemplo: si nosotros leemos el primer registro del cliente, el segundo, el tercero, el cuarto y después deseamos volver al segundo, la única forma de hacerlo consiste en cerrar el archivo y volver a abrirlo, ya que no podemos retroceder.

1.2.2.3 Los archivos secuenciales son monousuarios Los archivos secuenciales no permiten el acceso simultáneo (concurrencia) de varios usuarios. Si por desventura se accediera simultáneamente en modo escritura, los resultados son impredecibles: puede producirse corrupción de datos por escrituras entremezcladas o desaparición inadvertida de datos. El último que escribe tiene mayores posibilidades de mantener su información. Evitemos la concurrencia en archivos secuenciales.

1.2.2.4 Estructura rígida de campos Todos los registros deben aparecer en orden. Esto quiere decir que si nosotros escogemos el orden Nombre, Dirección, Población en el primer registro, no podemos cambiarlo por Dirección, Población, Nombre en el siguiente registro. El programa de lectura de un archivo secuencial va a ciegas leyendo líneas y necesita saber qué significado tiene cada línea según su orden.

24

© RA-MA

1

n

SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIÓN

Pero, ¿qué pasa si queremos grabar más datos de cada cliente? Por ejemplo su teléfono o su código fiscal, o sus condiciones de pago… La primera consecuencia es que debemos rehacer todos los programas de lectura para tener en cuenta estos nuevos campos. Y esto puede representar mucho trabajo si tenemos que acabarlo de un día para otro. La segunda consecuencia es que ese archivo ya no nos serviría para imprimir etiquetas. Tendríamos que guardar un archivo central con todos los datos y, a partir de éste, extraer en otro archivo sólo los datos que deseamos imprimir. Tras ello ya podríamos lanzar el nuevo listado por la impresora. Por tanto, debemos crear un nuevo proceso y complicar el que ya teníamos.

1.2.2.5 El modo de apertura condiciona lectura o escritura Las lecturas y las escrituras dependen del modo en que se haya abierto un archivo secuencial. En el momento de abrir un archivo, dependiendo del modo que hayamos escogido, quedaremos autorizados a leer o a escribir, pero no a las dos cosas.

1.2.2.6 Lecturas parciales pero escrituras totales Las operaciones de lectura pueden ser parciales, pero las operaciones de escritura conllevan obligatoriamente la escritura total de toda la secuencia completa de registros. Dicho de otro modo: al abrir un archivo en modo escritura estamos borrando su contenido anterior si lo hubiere. Por esta razón algunos lenguajes de programación contienen un modo de apertura llamado Append que escribe al final de un archivo existente en vez de reescribirlo de nuevo.

1.2.2.7 La marca de final de archivo (EOF) Las operaciones de lectura deben comprobar siempre que no rebasan el final del archivo secuencial, mediante la comparación del carácter de final de archivo (EOF o End Of File). Este carácter se coloca siempre y de modo implícito al cerrar un archivo secuencial en modo escritura.

25

GESTIÓN DE BASES DE DATOS

© RA-MA

1.2.2.8 Borrado de registros omitiendo contenido El borrado de un registro puede hacerse por varios métodos, aunque el más utilizado consiste en la escritura de todos los registros menos el que deseamos eliminar. Otro sistema es mantener la información, pero marcarla como borrada, lo cual implica hacer consideraciones de programación más complejas.

1.2.2.9 La posibilidad de uso de la marca de sincronismo Existe una posibilidad –realmente una técnica– que no se utilizaba en los primeros años del uso de los archivos secuenciales y que tiene que ver con la marca de sincronismo entre registros. La marca de sincronismo es una línea con un conenido específico que es palabra reservada. Es decir, si la marca que nosotros elegimos es , no puede haber ningún cliente que se llame ni ninguna dirección ni población que sea . Por tanto, cuando nosotros veamos en una línea un contenido aislado como la palabra reservada sabremos que se acaba un registro y a continuación empieza otro con el mismo orden. Esto nos permite crear registros con campos que tienen este orden: Nombre Dirección Población CIF Teléfono Email

26

© RA-MA

1

n

SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIÓN

Y nos permite también mezclar registros con diferentes estructuras, siempre que haya una parte inicial común: Nombre Dirección Población CIF Teléfono Email Nombre Dirección Población Nombre Dirección Población CIF Teléfono Email La técnica se basa en la lectura línea a línea. Cuando se descubre que el contenido de una línea es “”, sabemos que el siguiente campo es el primer campo del siguiente registro y que, por tanto, debemos omitir la lectura de los posibles campos que puedan seguir pertenecientes al registro actual.

27

GESTIÓN DE BASES DE DATOS

© RA-MA

1.2.2.10 Registros de longitud variable Los registros de un archivo secuencial tienen una longitud variable porque también sus campos tienen una longitud variable. No ocupa el mismo espacio un cliente que se llame Juan Sánchez, que otro cliente que se llame José María González de Castro y Santos de Carballar. Esto implica que a priori no vamos a saber el tamaño de las variables que debemos usar en memoria para almacenar estos contenidos. Para superar este tipo de problemas apareció el archivo de acceso aleatorio, que veremos más adelante.

1.2.2.11 Contenido legible en un procesador de textos El contenido de un archivo secuencial es legible en un procesador de textos. Pasó mucho tiempo antes de que aparecieran los editores de pantalla completa que permitían mover el cursor hasta la línea que queríamos con las flechas del teclado o con combinaciones de teclas.

El primero de ellos fue Wordstar y aquí ya empezamos a hablar de procesadores de textos. No funcionaban por comandos sino por combinaciones de teclas. En este momento las máquinas de escribir ya empezaban a estar amenazadas.

28

© RA-MA

1

n

SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIÓN

1.2.2.12 Consideraciones adicionales sobre los archivos secuenciales Los archivos secuenciales siguen siendo buenas opciones para almacenamiento de pocos registros en los que la velocidad de acceso no sea un punto clave. Todos los sistemas operativos soportan operaciones de lectura y escritura sobre archivos secuenciales. Todos los lenguajes de programación están dotados de funciones para acceder a archivos secuenciales. Los programas encargados de las altas, bajas, modificaciones, consultas, listados y otras operaciones que afectan exclusivamente a un archivo (por ejemplo, clientes) reciben el nombre de mantenimientos. Podemos, pues, realizar mantenimientos de archivos secuenciales mediante programas escritos en lenguajes de todo tipo: antiguos y modernos, como BASIC, Pascal, Fortran, COBOL, C/C++, Java, Visual Basic, C#, Prolog, LISP, etc. En nuestro caso vamos a utilizar cuatro lenguajes de gran difusión comercial y académica: 1. 2. 3. 4.

Visual C++. Visual Basic 6.0. Java. C#.

En las actividades encontraremos ejemplos en estos cuatro lenguajes.

1.3

ARCHIVOS DE ACCESO ALEATORIO

Si los archivos secuenciales se emparejan en el tiempo con el hardware de los tambores de cinta magnética, los archivos de acceso aleatorio aparecen con el disquete y el disco duro.

29

GESTIÓN DE BASES DE DATOS

© RA-MA

Los archivos de acceso aleatorio no están sujetos a la esclavitud de pasar por el inicio hasta llegar a la porción de la información que nos interesa. En los archivos de acceso aleatorio podemos colocarnos en una posición determinada expresada por un número. Por ejemplo, podemos ir directamente a la posición 100, volver atrás hasta la posición 20, avanzar ahora hasta la 200 y así tantas veces como queramos. Esto implica que si utilizamos una estructura delimitada en longitud, podemos calcular la posición en la que debemos situarnos para leer un registro. La medida básica de la posición del puntero de lectura es el byte; primer byte, segundo byte y así sucesivamente. Esto quiere decir que, si empleamos caracteres de dos bytes (por ejemplo, en Unicode), las posiciones para leerlos serán la 0, la 2, la 4, etc., avanzando cada vez de dos en dos. Pongamos por caso que tenemos un registro como éste codificado en ANSI (1 byte por carácter): Nombre: 80 caracteres ANSI n Dirección: 100 caracteres ANSI n Población: 50 caracteres ANSI n

Su longitud será de 230 caracteres. Esto implica que el primer registro se encontrará en la posición 0; el segundo registro se encontrará en la posición 230; el tercero estará en la posición 460 y así sucesivamente.

30

© RA-MA

1

n

SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIÓN

Por tanto, podemos decir que la posición será: Pos = NumRegistro * LongitudRegistro Si en cambio codificamos los caracteres en Unicode (UTF-16) de forma que su longitud es de 16 bits por carácter, esto es 2 bytes, el registro quedará así: Nombre: 80 caracteres UTF-16. n Dirección: 100 caracteres UTF-16. n Población: 50 caracteres UTF-16. n

Su longitud será de 460 caracteres para un solo registro, ya que cada carácter ocupa 2 bytes.

Ya tenemos la manera de calcular la posición. Ahora, cada lenguaje de programación dispondrá de su propia función para el posicionamiento del cursor de lectura o de escritura para realizar el acceso aleatorio.

1.3.1 ¿Qué sucede si un campo es de tipo numérico? En los archivos secuenciales se guardaba el número con su formato expresado en decimal: dígito a dígito. Por tanto, el número “10” ocupaba 2 caracteres y el número “1234567” ocupaba 7 caracteres. En los archivos aleatorios no se guardan los dígitos, sino el valor binario. Un número entero simple de 16 bits (de 0 a 65535) emplea 2 bytes.

31

GESTIÓN DE BASES DE DATOS

© RA-MA

Si se trata de un número entero de 32 bits (de 0 hasta 4.000 millones aproximadamente) ocupa 4 bytes. Si se trata de un número en coma flotante (normalmente se ajustan a la norma IEE488 como Excel) usa 8 bytes para almacenar mantisa y exponente. Estos datos ya no son legibles con un procesador de texto y si intentamos leerlos nos aparecerán caracteres extraños, con posibilidad de que el contenido no aparezca entero, ya que es frecuente encontrar un valor binario que coincida con el valor EOF (final de archivo).

1.3.2 Características de los archivos de acceso aleatorio

1.3.2.1 Posicionamiento inmediato Permiten situar el puntero de lectura o escritura sobre una posición concreta del archivo sin necesidad de pasar por las posiciones anteriores, con el consiguiente incremento de rapidez. Una sola apertura proporciona la capacidad de avanzar y retroceder sin necesidad de reabrir el archivo.

1.3.2.2 Registros de longitud fija Todos los registros tienen la misma longitud, ya que se utiliza siempre una estructura rígida dimensionada a la máxima longitud para cada campo.

1.3.2.3 Apertura para lectura/escritura Permiten su apertura en modo mixto (lectura y escritura), de forma que con una sola operación de apertura podemos leer o escribir a voluntad en cualquier posición según nos convenga.

1.3.2.4 Permiten el uso concurrente (multiusuario) Al establecerse zonas específicas y limitadas de actuación para lectura y escritura, diversos usuarios pueden acceder y escribir en diferentes porciones del archivo de forma simultánea.

32

© RA-MA

1

n

SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIÓN

Esto lleva a considerar la posibilidad de concurrencia de dos usuarios en el mismo registro. Para ello se utilizan algoritmos de gestión de los bloqueos. Dichos algoritmos administran zonas (que no siempre coinciden con registros) y las marcan para evitar dicha concurrencia de forma temporal. El tema del bloqueo lo trataremos más adelante dentro de los capítulos dedicados a bases de datos relacionales.

1.3.2.5 Dimensionamiento máximo al ser creados Los archivos de acceso aleatorio deben dimensionarse hasta un número de registros máximo en el momento de crearse.

1.3.2.6 Borrado de registro mediante ceros El borrado de un registro se realiza poniendo a 0 el espacio que ocupa; rellenándolo con bytes con el valor binario 0. En sistemas más complejos se emplea un algoritmo de reutilización de gaps o espacios vacíos, o incluso de compactación. Si empleamos un algoritmo de compactación de registros de gaps, deberemos ser conscientes de que el número de registro cambiará para un cliente dado en el momento en que se reubica, por lo cual una clave de acceso basada en número de registro no tendrá validez. Si utilizamos un algoritmo de reutilización de gaps deberemos ser concientes de que un cliente nuevo puede reutilizar el espacio de un cliente borrado. Por tanto, si utilizamos referencias a su número de registro en otros archivos, deberemos ser cuidadosos de que un cliente no sea falsamente referenciado en otros archivos. Estos son problemas de integridad referencial que se resuelven mejor en sistemas gestores de bases de datos, como veremos más adelante, y que fueron una de las razones para realizar el cambio desde el sistema de información basado en archivos al sistema de información basado en bases de datos.

33

GESTIÓN DE BASES DE DATOS

© RA-MA

1.3.3 Consideraciones adicionales sobre los archivos de acceso aleatorio Los archivos de acceso aleatorio están especialente indicados para aquellos casos en que el código del registro (cliente, proveedor, etc.) pueda ser directamente el número de registro en el que se guardan los datos. Al trabajar con archivos de acceso aleatorio deberemos tener en cuenta no rebasar nunca el final de archivo. Si nuestro archivo está dimensionado hasta 100 registros, intentar que no haya ningún usuario que nos pregunte por el 101 o por el 200. Para ello deberemos establecer nuestros sistemas de prevención desde el interfaz o desde el sistema de cálculo de la posición del puntero de lectura / escritura. Los archivos de acceso aleatorio son un paso más que nos conduce por el camino de los archivos indexados, puesto que constituyen el depósito de los datos. Como veremos más adelante, el almacenamiento temporal o no de las claves es el elemento que lo diferencia de los indexados.

1.4

ARCHIVOS INDEXADOS

Los archivos indexados son básicamente archivos de acceso aleatorio a los que se añade una utilidad para acceder al registro deseado a través de una clave. En el caso de los archivos de acceso aleatorio, la clave es siempre el número de registro. Los archivos indexados pueden buscar un cliente según su nombre, según su código de identificación fiscal o según cualquier otro campo. Para ello se construye una estructura de índice por cada campo que se desea indexar. Esta estructura de índice se mantiene en la memoria RAM de forma ordenada, de manera que podamos encontrar rápidamente una relación entre el apellido de un cliente y el número de registro en el que se encuentra.

34

© RA-MA

1

n

SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIÓN

Esto es lo que permite realizar las búsquedas por clave sin necesidad de recorrer todos los registros de la base de datos. Tradicionalmente, la estructura de información utilizada para localizar los registros por clave es el árbol binario o árbol de índices.

1.4.1 Historia y funcionamiento básico de los árboles de índices En el año 1962, Giorgi Maxímovich Adelson-Velskii y Yevgueni Mijáilovich Landis, dos matemáticos rusos, crearon un sistema de acceso muy rápido llamado árbol AVL (Adelson-Velskii-Landis). Un árbol se compone de nodos, que son los que contienen la información de la clave y del número de registro en donde se encuentran los datos que nos interesan. Dentro de un nodo tenemos:

1. El propio valor de la clave. 2. Un dato útil para referenciar en donde se encuentran los campos del registro, como por ejemplo, un número de registro para ir a buscar los datos. 3. Un puntero hacia un nodo que contenga una clave con un valor inferior o un nulo si no la hay, a la que llamaremos puntero L (de left o puntero a la izquierda). 4. Un puntero hacia un nodo con una clave mayor o un nulo si no la hay, a la que llamaremos R (de right o puntero a la derecha). 5. Otros datos interesantes para conocer rápidamente el estado del árbol, como por ejemplo la altura del nodo respecto a la base del árbol o el factor de equilibrio, que son datos que veremos más adelante. Los árboles binarios se representan al revés, como una coliflor boca abajo, en la que la raíz está siempre arriba.

35

GESTIÓN DE BASES DE DATOS

© RA-MA

Veamos un ejemplo de árbol en el que ordenaremos números:

A la izquierda de cada nodo colgamos un elemento más pequeño que el propio y a la derecha colgamos un elemento más grande. En todos los procesos de búsqueda mediante árboles, se entra a buscar siempre por la raíz. Imaginemos que estamos buscando el número 4. Entramos por la raíz, que es el 5. ¿Es éste el que buscamos? No. ¿Es menor? Sí. Nos vamos hacia la izquierda. Encontramos el 3. ¿Mayor, menor o igual que 4? Mayor. Nos vamos hacia la derecha y lo encontramos. Hemos realizado 3 comparaciones hasta llegar al dato que buscamos. Esto es más lógico que emplear una lista ordenada, ya que en una lista los números se organizarían así: 1 2 3 4 5 6 7

En el caso de buscar el mismo número, el 4, el número de comparaciones sería el mismo que empleando un árbol. Si buscásemos el número 2 en la lista, el número de comparaciones sería 1, más rápido que con el árbol.

36

© RA-MA

1

n

SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIÓN

En cambio, si buscáramos el 7, deberíamos hacer 6 comparaciones; mucho más lento, puesto que el árbol sólo tiene 3 niveles. En un árbol de 8 elementos, la altura máxima del árbol es de 3 niveles. No hará falta nunca rebasar 3 comparaciones para llegar al dato que buscamos, independientemente de si es grande o pequeño. En una lista ordenada, el número de comparaciones crece linealmente en función de la cantidad de elementos que almacenamos en la lista. En cambio, con el árbol, el número de comparaciones queda mucho más contenido. Comparemos el peor de los casos en cada sistema.

Tabla 1.1 Árbol

Lista ordenada

8 elementos

3

8

16 elementos

4

16

32 elementos

5

32

64 elementos

6

64

128 elementos

7

128

Si nos fijamos, veremos que 8 es 23. Por tanto, en un árbol de N elementos, el número de comparaciones máximo es el logaritmo en base 2 de los elementos contenidos. Los árboles ya se conocían antes de Adelson-Velskii y Landis. Eran y son llamados árboles BST o Binary Search Tree, pero a pesar de que agilizaban el acceso a los datos, se podían mejorar. ¿Por qué? Porque los árboles que empezaban teniendo 10 o 15 elementos eran muy rápidos, pero cuando iban creciendo existía el riesgo de crecer de forma asimétrica; se iban descontrolando; crecían de forma asimétrica. La palabra asimétrica expresa un crecimiento desequilibrado en el que unas ramas acaban siendo mucho más largas que otras, causando una desproporción en el número de pasos que deben darse (número de comparaciones necesarias) para llegar hasta encontrar una clave dependiendo de en qué rama se encuentre.

37

GESTIÓN DE BASES DE DATOS

© RA-MA

Este árbol respeta las normas L