From 35461b28428de0b91e4e2151d86ead1b1c7feb3b Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Mon, 31 May 2004 09:27:03 +0000 Subject: [PATCH] Agrego funciones de busqueda y recorrida secuencial del B+ --- doc/informe_2da_entrega.lyx | 68 +++++++++++++++++++++++++++++++++++-- 1 file changed, 66 insertions(+), 2 deletions(-) diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx index 1e9f612..65f4e09 100644 --- a/doc/informe_2da_entrega.lyx +++ b/doc/informe_2da_entrega.lyx @@ -480,7 +480,7 @@ n+1 n+1 \series default \emph default - (secuence set) contiene las claves mayores o iguales ya que el + (sequence set) contiene las claves mayores o iguales ya que el \begin_inset Quotes eld \end_inset @@ -639,7 +639,71 @@ Si el registro a eliminar fuera el primero del bloque, habr \layout Standard En cualquier otro caso, solo se eliminará el registro correspondiente y - se justificarán los regitros a izquierda. + se justificarán los registros a izquierda. +\layout Subsection + +Búsqueda +\layout Standard + +El proceso de búsqueda de un registro por su clave de identificación primaria + en la Organización Secuencial Indexada, es bastante directa en su entendimiento. + Para buscar un registro, acudiremos al árbol B+ con la clave anteriormente + mencionada, y obtendremos del mismo, el numero de bloque donde se debe + encontrar el registro. +\layout Standard + +Para obtener dicho número de bloque, el árbol internamente busca el ancla + menor inmediata a la clave buscada y luego devuelve el número de bloque + de datos donde está dicha ancla (el nro bloque será el dato asociado a + la clave ancla, en el árbol), el cual será el bloque potencial donde se + encuentre el registro buscado. +\layout Standard + +Una desventaja de esta implementación con indexación parcial, es que no + sabremos si el registro se encuentra efectivamente en el bloque indicado, + hasta no buscarlo dentro del mismo en formal secuencial. + Si lo hallamos, daremos por finalizada la búsqueda del registro. +\layout Subsection + +Recorrida secuencial de registros +\layout Standard + +Una consecuencia importante de la organización secuencial indexada, en este + caso implementada a través de un árbol B+ con indexación parcial, es que + como mencionamos anteriormente, los registros dentro de un bloque se encuetran + ordenados, y si bien los bloques en si pueden estar no ordenados en el + archivo de datos, algunos lo estaran, y minimizarán en base a estas cosa + características, los tiempos de acceso para una recorrida secuencial de + registros. +\layout Standard + +Suponiendo que nos encontramos con varios registros cargados en esta organizació +n de archivo, y con el correspondiente árbol de indexación primaria B+ en + el disco, si se nos pidiera por ejemplo, recorrer los registros de articulos + desde el ID_Articulo 40, hasta el ID_Articulo 1406, la operativa será la + siguiente: +\layout Itemize + +Acudimos al árbol y obtenemos el numero de bloque para el ID_Articulo 40, + buscando el ancla menor inmediata y obteniendo el nro de bloque de datos + donde se encuentra, siendo este el nro de bloque donde debería estar el + artículo de clave ID_Articulo 40. +\layout Itemize + +Levantamos el bloque de datos y lo recorremos secuencialmente, pues como + dijimos anteriormente, sus registros se encuentran ordenados por la clave + de identificación primaria, en este caso ID_Articulo. +\layout Itemize + +Cuando ya hallamos procesado todo el bloque, debemos obtener la siguiente + ancla a través del árbol y repetir el proceso. +\layout Itemize + +NOTA: Cabe desatacar, que todas las anclas estan en las hojas del B+, y + por ello las recorremos a nivel hojas a traves del Sequence Set, que gracias + a su encadenamiento, nos permite obtener en forma muy directa y efectiva, + las anclas de bloque ordenadas en secuencia, y por consiguiente, recorrer + el archivo en forma secuencial minimizando accesos. \layout Chapter Ordenamiento Externo -- 2.43.0