Go Down

Topic: Gestión e indexación de registros de una tabla en SD. (Read 14240 times) previous topic - next topic

noter

Dec 23, 2014, 04:21 pm Last Edit: May 27, 2015, 11:24 pm by noter Reason: Versión librería 1.0
Hola.
Pues dada la inquietud que surgió a raiz de la solución dada a un post sobre software, podemos intentar crear una librería para gestión de una tabla en SD con un número de registros considerable.
Establezco como punto de partida el último post de maxid para comenzar con las disertaciones previas:
llego tarde pero tengo varias ideas.

Primero encontré que la libreria SD.h hereda de Stream por lo que tiene un metodo Find, probé en un ejemplo y compila, no tengo una sd para probar.


Con respecto al tamaño, de claves lo vengo pensando hace rato porque tengo un proyecto que lo usa y lo tengo en espera.
les comentos algunas opciones
  • Si lo accedes de una pc ya lo envias ordenado en el archivo.
  • Un metodo que usaba novell, era calcular un hash de la posicion aproximada, desde ahi para abajo seguia buscando secuencialmente, esto permite una busqueda muy rapida
  • Otra es tenerlos ordenados e ir comparando el primer caracter solo, si no coincide pasar a la siguiente linea, si coincide seguir con el segundo caracter. Mejora el rendimiento ya que no hay que leer la clave completa.
  • Tambien se puede armar una cache de claves mas usada y primero leer ahi despues en el resto, que puede estar en un array en la eprom o en ram misma


Propongo como punto de partida (creo que ya tiene implementadas cosas muy buenas) la librería ExtendedDatabaseLibrary. Si os parece, intentaremos modificarla para enfocarla totalmente a archivo SD, y ampliarla para dotarla de funciones de búsqueda e indexación.

noter

PREMISAS A TENER EN CUENTA:

  • Los campos y registros deben ser de la misma longitud. De esta forma, siempre podremos predecir en qué posición buscar un determinado campo de un determinado número de registro (num_registro * lon_registro + despl_campo). La librería de la que partimos utiliza una estructura de usuario como registro, con lo que con esa estructura ya disponemos de los dos parámetros (longitud de registro y desplazamiento de campo). Si bien, como decía maxid, disponemos del método find, éste no nos va a ser muy útil, pues sólo debemos buscar el dato que nos interesa dentro de una parte (campo) de cada registro, y no dentro de todo el archivo.
  • El sistema de búsqueda sobre un archivo ya ordenado no debiera ser difícil, y se asemeja a lo que nosotros haríamos con un diccionario: se compara el valor buscado con el de la mitad de la tabla; si es mayor, desechamos la mitad inferior de la tabla y comparamos con el registro que está en la mitad de la otra parte, y así sucesivamente. El número de comparaciones necesarias vendrá dado por el "número de bits del número de registros" (p. ej. 16 comparaciones para buscar entre 65000 registros).
  • El mantener el orden en el archivo a medida que se haga más grande y agreguemos, borremos, o modifiquemos el campo es lo que nos va a dar verdaderos quebraderos de cabeza :)

surbyte

Bien, Noter como siempre lo has planteado de las mil maravillas.
Creo que también debemos establecer un criterio que establezca cuando es necesario mantener el orden del archivo y cuando no.
La librería EDB (extended database Library) trabaja sobre EEPROM del AVR, EEPROM serial externa o SD.
No es lo mismo reescribir en un AVR 100k lecturas/escrituras posibles, una serial que creo tiene 1millon y una SD que no me importa porque la cambio si se daña, claro que a costa de perder la DB Data Base.

Creo que en algún momento este punto debería contemplarse.

Voy a transcribir un texto muy corto pero muy indicativo de lo que se va a hacer y es para quienes comiencen a leer este proyecto y sepan de que estamos hablando.

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.

Una estructura de datos define la organización e interrelación de estos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:

    Alta, adicionar un nuevo valor a la estructura.

    Baja, borrar un valor de la estructura.

    Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datos estén ordenados).

Otras operaciones que se pueden realizar son:

    Ordenamiento, de los elementos pertenecientes a la estructura.
    Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.

Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

 
Todas las búsquedas se organizar alrededor de estos métodos de manera que conocer la teoría es un buen comienzo.

noter

Hola, surbyte.
De momento estoy con el esqueleto. Se trata de una librería con plantilla, ya que es la única forma que he encontrado para poder recibir de los sketch las dos piedras de toque en las que me voy a basar.
Para ir abriendo boca:
Básicamente, para crear un objeto, se deben definir una estructura de datos (con los datos que van a componer un registro) y una función que pueda comparar dos estructuras de ese tipo y devuelva si la primera es mayor, menor o igual que la segunda. La librería tomará esa estructura y esa función para realizar las búsquedas y ordenaciones.
La tabla contendrá un header, un índice (según la función que le vamos a enviar) y los datos en sí.
Espero poder poner en breve las primeras pinceladas, para ver qué se puede mejorar o agregar.

noter

Menuda lata con la plantilla. Me estaba volviendo loco, porque me daba errores el compilador de cosas no encontradas. Finalmente, tras mucho buscar y devanarme los sesos di con el problema:

SI ALGUNA VEZ TRATÁIS CON PLANTILLAS NO IMPLEMENTÉIS SUS MÉTODOS EN UN ARCHIVO .CPP.

Se puede ubicar todo el código en el propio archivo.h o se puede realizar un #include desde el propio archivo de cabecera (osea al revés) de otro archivo con extensión distinta a cpp. Es la forma por la que opté finalmente.

Bueno; pasada la primera en la frente, pongo el código del esqueleto en el primer post (no esperéis que funcione ni de broma :) ), y así comento mis primeros dilemas.

noter

A TORTAS CON LA ESTRUCTURA



La verdad es que para la mayoría de las aplicaciones arduino que se suele utilizar un archivo de datos, bien no sería necesario utilizar un archivo indexado (si el número de registros no es elevado) o bien el propio archivo sería un índice en sí. Recuerdo, por ejemplo, un proyecto en el que había que cotejar un número de teléfono (remitente de SMS) para comprobar si estaba en la tabla. Tres opciones a priori:

  • Archivo de texto con los teléfonos desordenados. Cotejar secuencialmente hasta encontrar o final de archivo. ¿Con cuántos registros empieza a ser pesado? (No lo sé, ya que no lo he comprobado. Era una pregunta retórica :P ).
  • Archivo binario con los teléfonos desordenados. Cada teléfono se podría codificar como un unsigned int, con lo que en lugar de 9-10 bytes por teléfono usaríamos 4 (mitad de espacio, doble eficiencia)
  • Archivo binario ordenado. Necesitaremos más tiempo cada vez que debamos agregar un registro, pero la búsqueda de un registro existente se puede realizar con cierta velocidad, dividiendo la tabla sucesivamente en mitades.


Hasta aquí nos podríamos desenvolver para las situaciones más habituales, así que no sé si realmente tiene mucho sentido lo que he comenzado a desarrollar. No obstante, como ya metí las dos piernas en el barro, intentaremos llevarlo hasta el final.

Supongamos que queremos guardar una serie de datos con un campo clave, por ejemplo
DOCUMENTO (campo clave), NOMBRE, TELÉFONO, DIRECCIÓN. Evidentemente, podríamos guardarlos ordenadamente según su número de documento en la tabla pero, suponiendo que la longitud de registro sea de 100 bytes y tengamos almacenados 1000 registros y queremos insertar uno que (oh, cielos) le corresponde el principio de la tabla, tendremos que mover 100 k de datos para hacerle hueco al nuevo registro. ¿Alguien podría calcular o comprobar directamente (en estos momentos no tengo a mano mi arduino) con qué velocidad de escritura contamos? (Según mi cálculo con los dedos medio mega por segundo)
Lo digo por tomar esta vía o complicarlo un poco más (crear un índice separado de los datos.

surbyte

Bien lo que he visto Serafín que el tema de la base de datos se esta volviendo una pregunta muy frecuente asi que este post luego tendra que convertirse en un tutorial para estos casos. Un FAQ.

NO se si te entendí bien, pero aca hay un post que discute velocidades de escritura en SD. van de 25kb/seg como muy bueno.
Yo lei en otro post 3kb/seg
A 25k eso implica 4 segundos para reescribir los 100k
A digamos 4k para hacer fáciles las cuentas son 25 seg para mover misma cantidad de datos.

noter

Bien; entonces creo que merecerá la pena el jaleo que estoy montando, de integrar en el archivo un índice y datos separados doblemente enlazados.
¿Sabéis qué creo qué me vendría muy bien, y a buen seguro que a muchos también? Un tutorial, o más bien una discusión con un post inicial dinámico con las cosas que saquemos en común sobre recomendaciones de estilo, porque cada vez que retomo un programa me doy cuenta de que cambio totalmente la "ortografía y gramática de la programación" y me quedan ilegibles. Paso de crear , por ejemplo variables en estilo MiVariable a miVariable, mi_variable, ulMiVariable... y al final acabo mezclando todo, con lo que me quedan unas chapuzas visuales... A buen seguro que a esta librería va a necesitar de una buena capa de maquillaje cuando la acabe para poder ser legible.
Bueno. Voy a seguir con ella. Creo que voy estando cerca de finalizar (seguro que con muchos fallos) la primera versión. Cuando la suba intentaré explicar cómo la estoy intentando desarrollar, a ver qué ideas podemos recabar para mejorarla.
Saludos.

noter

Hola de nuevo.
Llevo un par de días pegándome con el código y sin hacer una sola prueba con mi arduino, y ahora que parece que tengo algo con lo que empezar a hacer pruebas, no tengo el arduino a mano hasta el miércoles. La verdad es que tampoco me llevo muy bien con los módulos SD (no tengo shields) pues hasta ahora, no sé si por cableado, alimentación o qué, no consigo trabajar con la tarjeta con la librería SD, a no ser que baje la velocidad SPI.
Actualizo el proyecto al estado actual. He cambiado algunos conceptos de enfoque y nombres de métodos para intentar hacerlos un poco intuitivos. Para un primer vistazo a la librería, lo mejor es echar un vistazo al archivo FDB.h, y sobre todo a los métodos públicos de la clase (a ver si los entendéis, y si creéis que habría que cambiar algo).
Code: [Select]

template <class ESTRUCTURA>
class FDB {
public:
     // Constructor. Hay que pasarle una función que compare dos estructuras del tipo que vamos a registrar en BBDD
     // y devuelva si el índice del primero es mayor, menor o igual que el segundo.
     FDB( CompResult (*fcomparadora) (const ESTRUCTURA&, const ESTRUCTURA&) ):  _Compara(fcomparadora) { };

     // Devuelve número de registros en el índice (no borrados)
     IdReg count() {return(_head.filledRecords);};

     // Apertura de base de datos.
     Status open(char *nombreArchivo);

     // Si su index ya está en base, devuelve error; si no, lo da de alta.
     Status NuevoRegistro(const ESTRUCTURA&);

     // Lee el registro actual, y lo carga en la estructura registro espacio
     Status LeeRegistro(ESTRUCTURA &espacio);
     
     // Actualiza el registro actual con los datos dados. Si cambian datos de index, no debe permitir un índice existente.
     Status ActualizaRegistro(const ESTRUCTURA &espacio);

     // Elimina el registro actual
     Status BorraRegistro();

     // Busca el índice en una determinada posición. Si pedimos una posición fuera de rango ubica en EOF y devuelve ERR.
     Status IrRegistro(const IdReg &);
     
     // Busca el índice dado en una estructura y lo guarda en un IdReg dado. Si se localiza, la coincidencia devuelve ok.
     // Si no, guarda posición del primer registro mayor (posición de inserción) y devuelve ERR.
     Status EncuentraIndex(const ESTRUCTURA &, IdReg &);
     


Pienso que tal vez estoy abusando de parámetros por referencia. Claramente los datos de registro sí deben pasarse por referencia o puntero, pero los de índice (unsigned long) tal vez sea más práctico pasarlos por valor. No obstante, de momento me interesa saber si hace algo, aunque seguro que habrá errores. Si alguno probáis cosas (el archivo .ino es muy básico, pero si por casualidad funciona, se puede inentar probar modificaciones o borrados) me contáis.
Saludos.

noter

He modificado un poco el método NuevoRegistro, para que si existe previamente un index de registro eliminado, aproveche tanto el propio index como el espacio que ocupaba el viejo registro. Básicamente

Code: [Select]
  // Si existen registros borrados, aprovecharemos la posición de datos que apuntaba el índice anterior.
  if ( _head.deletedRecords > 0 ) {
    _LeerIndex(_registroActual, posDataInsertar);
    _head.deletedRecords--;
  } else {
    // Si no aprovechamos un borrado, los datos irán al final del archivo
    posDataInsertar = _dbFile.size();
    _EscribirIndex(_registroActual, posDataInsertar);
  }


Subo las modificaciones al primer post.

Sigo dirimiendo si utilizar paso y retorno de valores por valor, en lugar de mediante referencias, para los IdReg y FilePointer (ambos son tipo unsigned long). Tal vez resulte más intuitivo y menos propenso a posibles errores (se podrían pasar valores inmediatos).

surbyte

Noter: voy a hacer una simulación en Proteus 8.1 con un Arduino UNO y un Shield o una aproximación que permita leer un microSD.

Este es el mejor ejemplo que veo por ahora Esquema SparkFun microSD Shield.

Quote
/** SD card datalogger
 ** SD card attached to SPI bus as follows:
 ** MOSI - pin 11
 ** MISO - pin 12
 ** CLK - pin 13
 ** CS - pin 4
 */
Lo hice mas simple y esta como dice la lista de arriba.

noter

Hola.
Llevo un par de días intentando hacer funcionar un programa básico de SD en mi arduino (ReadWrite, y no hay forma. No sé si las dos lectoras están mal, o puede ser problema del IDE o la librería SD (estoy con el IDE 1.5.8 y la propia librería que ya trae el IDE). El caso es que consigo detectar SD y volumen (bajando a QUARTER_SPEED el SPI), pero no me lee ni escribe ningún archivo. Tal vez tenga que modificar la librería (igual en algún punto me vuelve a establecer la velocidad a HALF_SPEED).
¿Alguien podría decirme si para un slot de estos estilos

conectado al arduino por cables de unos 10cm ¿sería necesario algún condensador o similar para poder trabajar a velocidad normal (SPI_HALF_SPEED) con la SD?

Por otro lado, surbyte, ¿has conseguido simular la jodida dichosa SD en proteus? Tampoco he sido capaz de hacer funcionar ni un ejemplo. No sé si probar a retroceder de IDE, anque me da pereza.

surbyte

Si claro que si. Funciona perfecto.
Enviame un email y lo conversamos.

surbyte

Noter dame un código para probar con el simulador.

noter

Bueno. Al menos ya puedo probar sobre la placa real aunque, como dije, he tenido que modificar mi librería para que en lugar de SPI_HALF_SPEED trabaje en SPI_QUARTER_SPEED. Así que he comenzado a depurar (de momento el código no rula). A ver si estos días consigo avanzar un poco, aunque el trancazo que he pillado no permite que mi mente funcione con mucha lucidez.
Lo que no he sido capaz de hacer funcionar ha sido la SD en proteus. Mismamente el ejemplo ReadWrite del IDE, asignando un fichero de imagen a la tarjeta (un txt vacío) y las conexiones creo que bien realizadas (si modifico alguna, no hay comunicación ni errores SPI) lo único que consigo es un montón de errores "mmc command unsupported".
¿A tí te funciona correctamente, surbyte? ¿Alguien sabe a qué puede ser debido ese tipo de error?

Go Up