8. Acceso secuencial indexado y B+Trees

8.1 Indices para búsquedas y reportes

Hasta el momento hemos estudiado 2 tipos de estructuras de archivos (organización de archivos):

• Acceso secuencial: 
  • Archivos que pueden recorrerse secuencialmente (registros contiguos, sin necesidad de offset) regresando los registros en algún orden específico
• Indexamiento: 
  • Archivos de datos que poseen archivos de índices por diferentes llaves que permiten accesar los datos de distintas maneras, el archivo de datos se encuentra sin ningún orden (entry sequenced).

Problemas:

• Desafortunadamente el archivo secuencial es difícil de mantener.
• Los índices (aún usando un esquema de B-Tree) nos permiten hacer búsquedas rápidamente pero ...nos permiten recorrer el archivo secuencialmente ??
  • En realidad el B-Tree sí nos permite recorrer el archivo en orden, pero no en una manera sencilla ya que debemos hacer demasiados "seeks" para poder hacerlo.

En la práctica en muchas situaciones se requieren de ambas cosas (búsquedas y accesos secuenciales), por ejemplo:

• En la universidad
  • Búsquedas: horarios, adeudos, transcript
  • Secuenciales: Reportes de calificaciones que se imprimen
• En una empresa
  • Búsquedas: agenda telefónica, vacaciones
  • Secuenciales: cheques de nómina

Las 2 soluciones existentes:

• ISAM indexed sequential access method
• B+ Tree

8.2 Indexed Sequential Access Method (ISAM)

Básicamente es la idea de tener un índice esparcido, de manera que el archivo de datos lo agrupamos por bloques y en cada bloque existe un "rango" ordenado de los datos (Figura 8.1).

 

Figura 8.1

Lo importante a resaltar aquí es que los bloques no necesariamente están formando una secuencia en el archivo, es decir, dentro del archivo de datos los bloques pueden estar desordenados, aquí el detalle es mantener un apuntador a cada bloque subsecuente como se muestra en la figura 8.2.

Figura 8.2

Reglas generales para un índice ISAM:

• Podemos iniciar el archivo con un bloque o varios (definiendo previamente los rangos y dejando bloques vacíos reutilizables).
• Cuando agregamos datos ubicamos el bloque correspondiente en base al índice en memoria y procedemos a agregar la información.
• Si al insertar notamos que el bloque ya esta lleno entonces tenemos que partirlo en 2, muy similar al btree solo que aqui no necesitamos un separador de ramas, simplemente creamos otro bloque, dividimos equitativamente los datos y ajustamos los apuntadores entre los bloques
• Para eliminar, ubicamos el bloque y eliminamos el registro
  Si al eliminar notamos que se pueden mezclar o unir dos bloques con pocos registros entonces lo podemos hacer y el bloque libre lo marcamos para reutilización

Key	Block number
BERNE	1
CAGE	2
DUTTON	3
EVANS	4
FOLK	5
GADDIS	6

Tabla 8.1

La figura 8.3 muestra una primer solución de separadores basándose en los prefijos de las palabras. De esta manera nos evitamos el tener que estar actualizando constantemente el índice. Estos separadores de rangos nos son únicos, dependerá del programador el definirlos, la figura 8.4 nos muestra una lista de opciones para el caso de los bloques 3 y 4.

Figura 8.3

Figura 8.4

8.3 B+ Trees

Estas necesidades son el origen de los B+ Trees.
Un B+ Tree es muy similar a un BTree en muchos aspectos, la principal diferencia es que en las "hojas" se encuentran todas las llaves ordenadas, mientras que en los demás nodos se encuentran sólo algunas de ellas que sirven de camino para llegar rápidamente al nivel más bajo.

Aquí el orden se define como el número máximo de llaves que puede tener un nodo, cada nodo debe estar siempre al 50 % de su capacidad, excepto la raíz que al menos deberá tener 2 llaves (2 ligas); esto último después de haber pasado las inserciones iniciales donde obviamente la raíz podrá tener 1 sola llave.
Para el ejemplo de la Figura 8.5 el orden que estamos considerando es 4.

Inserción
Lo primero que se debe hacer es buscar en qué nodo hoja debe insertarse, analizando desde la raíz algunos de los nodos del árbol.
El insertar una llave en un nodo que no esta lleno es fácil sólo se actualiza el nodo, recordando que la llave "más grande" debe promoverse siempre al nivel superior.
Si se inserta en un nodo lleno entonces ocurre un "overfull" y el nodo deberá partirse en 2, promoviendo al nivel superior las llaves más grandes de los nuevos nodos.
Recordar que al igual que los b-trees muchas de estas operaciones pueden causar acciones recursivas al alterar los niveles superiores y en caso de llegar a la raíz entonces el árbol crecerá en un nivel.

Figura 8.5

Figura 8.6

Eliminación:

El proceso de eliminación se puede deducir del proceso de inserción.
Al eliminar una llave localizamos la hoja donde se encuentra la llave a eliminar y la eliminamos, aquí tendremos 2 opciones:

• 1) Se mantiene más de la mitad de las llaves del nodo
• 2) Se presenta un "underflow" al tener menos de la mitad de llaves en el nodo.

Para el primer caso lo único que se debe revisar es si la llave más grande sigue siendo la misma, si la llave que eliminamos era la más grande debemos actualizar el nivel superior (quizás sucesivamente si es el caso)
Para el segundo caso debemos "concatenar" dos nodos hermanos, teniendo 2 casos:

• a) formando un solo nodo donde la llave mayor se promueve actualiza al nivel superior.
• b) formando 2 nodos cada uno 1/2 lleno y actualizando en el nivel superior las 2 llaves mayores de cada nodo.

Nuevamente es importante recordar que las eliminaciones pueden caer en un proceso recursivo que llegue a la raíz en cuyo caso el árbol se reducirá en un nivel.

Figura 8.7

En esta sección se analizó el modelo conceptual de los B+ Tree y se omitieron detalles de implementación tales como la  relación que debe existir entre los nodos "hoja" para poder realizar un acceso secuencial (Figura 8.7) en ese nivel.

Resumiendo:

• Los B+ Trees son un caso especial de B-Trees
• La gran diferencia es que en las hojas se encuentran todas las llaves y los demás nodos sirven como camino a dichas hojas
• Se podría llegar a pensar que el hecho de duplicar las llaves en los distintos niveles del árbol es demasiado costoso pero en realidad no lo es ya que esa duplicidad ocurre en disco (actualmente demasiado barato) y si recordamos la diferencia de "orden" un árbol B+ Tree del mismo orden que un B-Tree ocupará menos espacio ya que no almacena refencias a los datos y podríamos elevar fácilmente su orden permitiendo tener árboles menos profundos; esto último desde luego éstos últimos permitiendo búsquedas en más corto tiempo.
• Se utilizan en casos donde se requieren tanto accesos aleatorios como secuenciales.

Nota: es importante mencionar que en la literatura muchos autores definen de maneras diferentes a los árboles, lo que para nosotros es un B+Tree para otros es un B-Tree, la nomenclatura empleada aquí es tomada del concepto original propuesto por Bayer, McCreight, Knuth y Comer.

---

8.4 Prefix B+ -Trees

Como su nombre lo indica son una modificación al algoritmo de B+ Trees

La característica de estos árboles radica en que el conjunto de llaves que NO son hojas del árbol (index set), no son llaves completas sino un "prefijo" (prefix) de dichas llaves, de manera que las llaves completas sólo existen en el nives más bajo (hojas del árbol).

Similar a B+ Tree las hojas del árbol en realidad son "bloques" de datos que se van ligando unos con otros por ejemplo:

Tabla 8.2

Lo que se pretende es que este prefijo sea del menor tamaño posible ya que recordemos que para cada nodo hoja la referencia que se tiene con el nodo superior es la llave de mayor tamaño. En el ejemplo de la figura 8.8 (un prefix b+tree de orden 2) podemos ver que la llave más grande del primer bloque sería "Berne" y el prefijo que nos sirve de separador es "Bo" de ahí lo que mencionábamos de la relación menor-mayor.

Figura 8.8

A diferencia de los árboles que hemos visto, aquí al eliminar una llave únicamente la eliminamos del nodo hoja, no se alteran los prefijos del resto del árbol. Esto facilita enormemente el proceso de eliminación y permite que de una manera sencilla se siga aprovechando ese prefijo para las nuevas inserciones.

Figura 8.9

Por otro lado el proceso de inserción si produce las operaciones que se explicaron anteriormente, en el ejemplo podemos ver que al agrega una llave nueva, se aumenta un nuevo bloque (7) y en consecuencia se agregar un nuevo separador (AY) al index set, formando el nodo (AY,BO,CAM) lo cual resulta en una división del nodo, produciendo entonces (AY) (CAM) y la promoción de (BO).

Figura 8.10

Finalmente una eliminación del bloque 3 puede causar un "underflow" y en consecuencia el bloque 2 y 3 deberán unirse para formar uno solo, en cuyo caso el separador (CAM) deja de utilizarse y forza a (BO) a que baje nuevamente.

Figura 8.11

Resumiendo:

• Los Prefix B+ Trees se recomiendan cuando las llaves completas ocupan demasiado espacio
• Se podría llegar a pensar que el mantener muchos prefijos de llaves eliminadas ocuparía mucho espacio pero nuevamente recordemos que estan en disco (muy barato) y que por ser prefijos su tamaño es mínimo.