READ TABLE .... BINARY SEARCH

BINARY SEARCH es una opción de la instrucción READ TABLE que realiza la búsqueda de un registro en concreto en una tabla interna utilizando un algoritmo de búsqueda binario. Los algoritmos de búsqueda binarios son mucho  más rápidos y eficientes que la búsqueda secuenciales. Pero, si utilizáis la opción BINARY SEARCH y no ordenáis correctamente la tabla,  al ejecutar el programa es  posible que no encuentre el registro en la tabla interna, aunque utilizando el debugger comprobereis que si que existe el registro que buscamos en la tabla interna.

En esta entrada del blog. Explicaremos la diferencia entre la búsqueda secuencial y la búsqueda binaria con la instrucción READ TABLE  y porque es necesario asegurarnos de que la tabla interna esta ordenada antes de realizar una búsqueda binaria.

READ TABLE: BÚSQUEDA SECUENCIAL

La instrucción READ TABLE busca un registro en la tabla interna especificada que cumpla una condición dada. Por defecto, a menos que la tabla interna sea de tipo SORTED o HASHED, la búsqueda del registro se realiza secuencialmente. Una búsqueda secuencial consiste en leer cada registro de la tabla de forma lineal, desde el primer registro al ultimo o  hasta encontrar un registro que cumpla la condición de la busqueda.

Búsqueda secuencial en una tabla interna

Da igual que ordenemos la tabla antes, la búsqueda sera siempre por defecto secuencial o lineal. Lo bueno de la búsqueda secuencial es que es muy simple de usar y siempre funciona. Por contra, como podéis ver en la imagen siguiente, es el método de búsqueda  que más tiempo consume.

Tiempos de acceso a una tabla interna con 100.000 registros

READ TABLE: BÚSQUEDA BINARIA

Una forma de acelerar la búsqueda es añadir la opción BINARY SEARCH a la instrucción READ TABLE. Esta opción realiza una búsqueda en la tabla interna utilizando un algoritmo de búsqueda binaria. Una búsqueda binaria comenzará examinando el registro central de la tabla interna. Si el registro es el que buscamos, hemos terminado. Si no es el registro correcto, podemos utilizar la naturaleza ordenada de la tabla para eliminar la mitad de los registros restantes. Si el registro que buscamos es mayor que el registro central, sabemos que no hace falta buscar en los registros anteriores al registro central. El registro que buscamos, si es que está en la tabla interna, debe estar en la mitad superior al registro central, ya que este es menor que el registro buscado. Podemos entonces repetir el proceso con la mitad superior. Buscamos el registro central de la parte superior y lo comparamos con el valor que estamos buscando. Una vez más, o lo encontramos o dividimos la lista por la mitad, eliminando por tanto otra gran parte de nuestro espacio de búsqueda posible.

Búsqueda binaria del registro con valor 20

Es importante ordenar la tabla antes por los campos que utilizamos para la búsqueda. Si no ordenamos la tabla antes de ejecutar la búsqueda binaria es posible que aunque el registro que buscamos exista en la tabla interna, nunca lo encuentre.

Por ejemplo, el siguiente código,  ordena la tabla antes de ejecutar la búsqueda binaria. 

Búsqueda binaria ordenando antes la tabla interna

El proceso de búsqueda seria:

1. Busca el registro medio de la tabla y compara el valor
2. El valor del registro 9 es mayor que el valor buscado
3. Busca el registro medio entre los registros 0 y 9.
4. El valor del registro 4 es mayor que el valor buscado
5. Busca el registro medio entre los registros 0 y 4
6. El valor del registro 2 es igual al valor buscado
7. EL puntero <FS_KUNNR> apuntara al registro 2 de la tabla TI_KUNNR y retorna sy-subrc = 0.

En cambio, si no ordenamos la tabla antes, no encontrara nunca el registro.

Búsqueda binaria SIN ordenar antes la tabla interna

El proceso de búsqueda seria:

1. Busca el registro medio de la tabla y compara el valor
2. El valor del registro 9 es mayor que el valor buscado
3. Busca el registro medio entre los registros 0 y 9.
4. El valor del registro 4 es mayor que el valor buscado....
5. Repite la búsqueda sin encontrarlo nunca porque ya no estan entre los registros seleccionados
6. retorna sy-subrc = 4.

CONCLUSIÓN

 Recordar siempre ordenar la tabla interna antes de usar  READ TABLE...BINARY SEARCH.

¿Y que pasa si  la tabla interna es SORTED?

Si estamos utilizando una tabla interna de tipo sorted. No hace falta indicar la opción BINARY SEARCH. Si utilizamos parte o todos los campos que forman la clave de la tabla interna, la búsqueda sera binaria por defecto. En cambio, si utilizamos campos de la tabla interna que no pertenecen a la clave principal, la búsqueda sera  siempre secuencial.

¿ Y las tablas HASHED?

Nunca se utilizan búsquedas binarias con tablas interna de tipo HASHED. Con las tablas hashed  se accede a cada registro de la tabla con una clave hash. No es necesario utilizar búsquedas binarias porque cualquier búsqueda utilizando tablas hashed, es mucho más rápido que utilizando búsquedas binarias.

PROGRAMA DE EJEMPLO

En el repositorio de GITHUB del blog os dejo un programa para ilustrar el caso:

Programa ZZREAD_TABLE_BINARY.

• El primer READ TABLE es secuencial.
• EL segundo READ TABLE es binario sin ordenar la tabla.
• El tercer READ TABLE es binario y ordena la tabla antes.