Grato por sua resposta. Estou aguardando a aprovação do GitHub dos dados fiscais que fui obrigado a fornecer. Deve ser liberado em breve. Colocarei um aviso no fórum.
Aquí está el esquema conceptual del motor de índice en disco implementado (DiskIndexedFile, contenedor PRCIDXD1).
Este es el formato persistente; el motor en memoria es un subconjunto simplificado del mismo modelo.
1. El archivo = un array de páginas fijas de 4 KiB
byte 0 end of file
┌────────┬────────┬────────┬────────┬────────┬──── ────┬───── ... ─────┐
│ Page 0 │ Page 1 │ Page 2 │ Page 3 │ Page 4 │ Page 5 │ ... │
│ HEADER │ B+tree │ B+tree │ DATA │ DATA │ DIR │ │
└────────┴────────┴────────┴────────┴────────┴──── ────┴───────────────┘
Cada página tiene exactamente PAGE_SIZE = 4096 bytes;
page id = desplazamiento en bytes / 4096
Cada página después de la página 0 se identifica por su primer byte (etiqueta de tipo):
| Tag | Page type | Contenido |
|-----|-------------|------------------------------------------------|
| 1 | PT_INTERNAL | Nodo interno de B+tree |
| 2 | PT_LEAF | Nodo hoja de B+tree (doubly linked) |
| 3 | PT_DATA | Página con slots que contiene varios registros |
| 4 | PT_OVERFLOW | Continuación para registros demasiado grandes |
| 5 | PT_DIR | Un fragmento del directorio de RecordId |
Las páginas pueden liberarse y reutilizarse mediante una free list, por lo que el orden físico en disco no corresponde al orden lógico.
2. Página 0 — el encabezado (se escribe una sola vez, es el único esquema del archivo)
PRCIDXD1 version page_size rec_fmt compressing record_len
(8 bytes) (u16) (u32) (u8=1) (u8 0/1) (u32)
────────────────────────────────────────────────── ────────────
next_page_id free_list_head record_count data_tail (cada u64)
primary_root dir_head directory_len (cada u64)
────────────────────────────────────────────────── ────────────
alt_root_count (u16) → [ alt_root : u64 ] × N (una raíz B+tree por clave alternativa)
────────────────────────────────────────────────── ────────────
KEY SCHEMA: key_count (u16) → para cada clave:
duplicates_allowed (u8)
part_count (u16) → [ offset:u32, length:u32 ] × partes (claves compuestas)
Nota: No hay nombres de campos ni metadatos por registro. El esquema solo define la geometría de las claves (rangos de bytes).
3. Ruta de acceso (cómo se resuelve un READ)
COBOL key value (bytes)
│
▼
┌──────────────┐ primary_root / alt_roots[k]
│ B+tree (uno │ por clave. Las páginas internas enrutan;
│ por clave) │ las hojas contienen (key_bytes → RecordId)
└──────┬───────┘ y están doubly linked para READ NEXT / PREVIOUS.
│ RecordId (un entero estable)
▼
┌──────────────┐ directory[RecordId] = RecLoc
│ Directorio │ { kind, page, slot, len }
│ de RecordId │ kind: 0=free/tombstone 1=inline 2=overflow
└──────┬───────┘
│ (page, slot)
▼
┌──────────────┐ slotted DATA page → slot dir → (offset,len)
│ DATA page │ → imagen raw del registro (opcionalmente comprimida)
└──────┬───────┘
▼
los bytes del registro de ancho fijo → RecordLayout.distribute()
los distribuye en los subcampos del FD en memoria.
Todos los índices (primario + alternos) apuntan al mismo RecordId, por lo que existe exactamente una copia de cada registro.
4. Una página PT_DATA vista en detalle
┌─ byte 0 ─┬─ 1..3 ─┬─ 3..5 ──┬─ slot directory ─────┬─ ... free ... ─┬─ record data ─┐
│ type=3 │ slot_ │ free_ │ (off:u16,len:u16) ×N │ │ packed │
│ │ count │ top │ grows → │ │ ← grows │
└──────────┴────────┴─────────┴─────────────────── ───┴───────────────┴───────────────┘
El directorio de slots crece desde el frente, los registros desde el final. Los registros más grandes que una página se desbordan en una cadena PT_OVERFLOW.
5. Imagen del registro (posicional, sin nombres)
Ejemplo: 01 CUST. 05 ID PIC 9(5). 05 NAME PIC X(10). 05 CITY PIC X(8).:
offset: 0 5 15 23
┌────────┬────────────────────┬────────────── ─┐
payload: │ 00001 │ John Doe │ Sao Paulo │ ← 23 bytes, fixed
└────────┴────────────────────┴────────────── ─┘
ID(5) NAME(10) CITY(8)
materialize() empaqueta los subcampos en este buffer; distribute() hace lo inverso. Con compresión, se aplica PackBits-RLE.
6. Estructuras transversales
* Free list — free_list_head encadena las páginas liberadas para reutilizar espacio.
* Directorio de RecordId — reside en RAM mientras el archivo está abierto, se persiste en páginas PT_DIR.
* Transacciones — undo log en RAM (inversas de Insert/Update/Delete). ROLLBACK las aplica; COMMIT las descarta y hace flush.
* Validación estricta en OPEN — compara el esquema de claves almacenado con el del programa; mismatch → file status 39.
En una oración: un archivo paginado compuesto por un header + N B+trees (uno por clave) → directorio de RecordId → páginas de datos con slots de registros de ancho fijo posicionales, con free list, cadenas de overflow, compresión RLE opcional y undo log para transacciones.
|