Busqueda en una aplicacion de bases de datos

Imaginemos un master file, perteneciente a una base de datos, que contenga records de clientes ordenados por nombre del cliente. Como seria la busqueda de un record en la cinta dado el nombre del cliente?

La solucion trivial es busqueda secuencial, la cual consumiria 15 minutos en el peor de los casos. Pero tratemos de usar un algoritmo de busqueda, biparticion:

La busqueda comienza en la mitad de la lista. Si la clave alli encontrada es menor que la buscada, entonces la respuesta esta en la otra mitad de la cinta, si no, esta en la mitad anterior; se avanza pues (adelante o atras segun el caso) hasta la mitad de la mitad de la lista y se procede recursivamente hasta que se encuentre el elemento buscado. En terminos practicos, el algoritmo termina cuando el tramo a buscar es suficientemente pequenno, entonces se procede a hacer busqueda secuencial en ese tramo.

Como implementamos esto en la cinta de la Otari?

De hecho, no es posible avanzar (o retroceder) hasta "la mitad de la cinta" pues el drive no puede calcular la posicion de la cinta con esa presicion; sin embargo podemos aproximarnos a esa meta usando un recurso de la Otari: Los pulsos del TACOMETRO, los cuales se ofrecen en su Puerto Paralelo.

La frecuencia de estos pulsos es proporcional al desplazamiento de la cinta con independencia de la velocidad ya que el tacometro esta colocado en una rueda por donde pasa la cinta siempre. No aspiro a poder contar a nivel de "bytes", ni siquiera de bloques, pero si a tener un numero que es aproximadamente proporsional al desplazamiento de la cinta.

Contando estos pulsos mientras se rebobina la cinta, el Controlador puede calcular con aproximacion la magnitud del desplazamiento. De hecho, se puede tener un numero a priori (desde disenno, o tal vez configurable) que se corresponda con el desplazamiento total de la cinta, y usarlo con un "maximo".

Se me ocurre que el programa puede pedirle al controlador que rebobine la cinta "tantos pulsos" hacia adelante (o hacia atras). El controlador manda a rebobinar, se mantiene contando pulsos y cuando llegue a la meta, manda STOP.

Estamos hablando entonces de un comando SEEK con un argumento numerico que indica el numero de pulsos a contar. Es ya responsabilidad del programador figuarse cual es al argumento adecuando en cada caso. Habria otra operacion complementaria SEEK_BACK.

Con estas operaciones implementadas, se pueden escribir programas que manden a mover la cinta hacia atras o hacia adelante a fin de acercarse gradualmente a la informacion buscada.

Tal vez sea buena idea ajustar el conteo de pulsos en el device driver de manera que el argumento de SEEK sea un entero entre 0 y 100 donde este ultimo corresponde con el maximo conteo (toda la cinta). De esta forma, el programador puede pensar el argumento en terminos de porcentaje.

Mas aun: el device driver puede combinar SEEK and SEEK_BACK en un solo comando cuyo argumento puede ser posivo o negativo. O incluso cero, en cuyo caso se haria una operacion SEEK_EOT.

Han de implentarse las siguientes operaciones:

SEEK count
    Avanza la cinta leyendo el tacometro hasta que la cuenta llegua a 'count',
    entonces entra en modo PLAY y avanza hasta el proximo GAP donde se detiene
    (STOP)

SEEK_BACK count
    Igual que SEEK pero en Rewind.

REWIND
    Rebobina hasta inicio de la cinta.
    => Solo tiene sentido si se puede implementar un mecanismo "BOT" tal que al
       rebobinar la cinta no se salga del carrete. De lo contrario, mejor dejar
       el rebobinado en manos del Operador.

FF => No hace falta una operacion Fast Forward pues no es util para nada.