VisualDatabase
Wie funktioniert eine dBase-Datenbank im Inneren? Diese App zeigt die physischen DBF-Strukturen, den passenden C-Code und – als Herzstück – den B-Tree-Index mit animiertem SELECT-Zugriff in verschiedenen Geschwindigkeiten.
Aufbau eines DBF-Datensatzes
Eine dBase-Tabelle speichert Datensätze mit fester Breite. Aus dem Kopf der Datei und den Feld-Deskriptoren ergibt sich, wo jeder Satz und jedes Feld liegt.
📐 Aufbau der DBF-Datei
Feld-Deskriptoren
| Feld | Typ | Länge | Dezimal |
|---|---|---|---|
| NAME | C (Character) | 20 | 0 |
| STREET | C (Character) | 25 | 0 |
| CITY | C (Character) | 18 | 0 |
| ZIP | C (Character) | 5 | 0 |
🔬 Datensatz als Bytes
Datensatz #1 liegt bei Offset 0xA1. Jedes Zeichenfeld hat feste Breite und ist rechts mit Leerzeichen (␣) aufgefüllt.
→ Wegen der festen Breite kann dBase jeden Satz per Offset-Rechnung direkt anspringen: offset = header_size + (recno − 1) × record_size
Die DBF-Strukturen in C
So sehen die Strukturen aus, mit denen ein dBase-Treiber den Dateikopf, die Feld-Deskriptoren und einen Adress-Datensatz im Speicher abbildet.
/* DBF-Dateikopf - exakt 32 Bytes, am Dateianfang */struct DBF_Header { uint8_t version; /* 0x03 = dBASE III ohne Memo */ uint8_t year; /* Jahr der letzten Aenderung (JJ-1900) */ uint8_t month; /* Monat (1..12) */ uint8_t day; /* Tag (1..31) */ uint32_t num_records; /* Anzahl Datensaetze in der Tabelle */ uint16_t header_size; /* Bytes bis zum 1. Datensatz */ uint16_t record_size; /* Bytes pro Datensatz (inkl. Loeschflag)*/ uint8_t reserved[20]; /* reserviert / Transaktionsflags */};/* Feld-Deskriptor - 32 Bytes je Spalte, direkt nach dem Header */struct DBF_Field { char name[11]; /* Feldname, mit 0x00 terminiert */ char type; /* 'C','N','D','L','M' (Datentyp) */ uint32_t data_address; /* Adresse im Speicher (zur Laufzeit) */ uint8_t length; /* Feldlaenge in Bytes */ uint8_t decimal_count; /* Nachkommastellen (nur Typ 'N') */ uint8_t reserved[14]; /* reserviert */};/* Ein Datensatz der Adress-Tabelle - feste Breite 69 Bytes */struct AddressRecord { char deleted; /* 0x20 = aktiv, 0x2A ('*') = geloescht */ char name[20]; /* NAME - rechts mit ' ' aufgefuellt */ char street[25]; /* STREET - rechts mit ' ' aufgefuellt */ char city[18]; /* CITY - rechts mit ' ' aufgefuellt */ char zip[5]; /* ZIP - Postleitzahl */};/* NDX-Indexseite - klassisch 512 Bytes pro Knoten ("Page") */struct NDX_Page { uint16_t num_keys; /* belegte Schluessel auf dieser Seite */ struct { uint32_t lower_page; /* Zeiger auf Kindseite (kleinere Keys) */ uint32_t record_no; /* Satznummer im DBF (recno) */ char key[KEYLEN];/* Schluesselwert, z.B. NAME */ } entry[ORDER]; uint32_t rightmost; /* Zeiger auf rechteste Kindseite */};Dateikopf verstehen & einen Datensatz dynamisch einlesen
Der Header definiert über die Feld-Deskriptoren, welche Spalten mit welcher Länge existieren. Mit vereinfachtem C liest man den Kopf, berechnet die Feld-Offsets und zerlegt jeden Datensatz generisch – ohne ein fest verdrahtetes struct pro Tabelle.
🧱 Der Dateikopf (Header) – 32 Bytes
Der Header steht ganz am Dateianfang und beschreibt die Tabelle: Version, Änderungsdatum, Anzahl Datensätze sowie – entscheidend für den Direktzugriff – header_size und record_size. Direkt danach folgt für jede Spalte ein 32-Byte-Feld-Deskriptor; deren Reihenfolge und Längen sind frei wählbar.
| Offset | Größe | Feld | Bedeutung | Beispiel (ADDRESS.DBF) |
|---|---|---|---|---|
| 0 | 1 B | version | Dateityp / dBASE-Version | 0x03 (dBASE III) |
| 1 | 3 B | date (YY MM DD) | Datum der letzten Änderung | 126 06 18 |
| 4 | 4 B | num_records | Anzahl Datensätze (uint32, little-endian) | 12 |
| 8 | 2 B | header_size | Bytes bis zum 1. Datensatz | 161 |
| 10 | 2 B | record_size | Bytes pro Datensatz | 69 |
| 12 | 20 B | reserved | reserviert / Transaktions- & Sprachflags | 0x00 … |
📐 Felder verschiedener Länge definieren: Jeder Feld-Deskriptor trägt seine eigene length. NAME = 20 B, STREET = 25 B, CITY = 18 B, ZIP = 5 B. So entsteht eine dynamische, pro Tabelle unterschiedliche Satzstruktur.
Kopfbereich gesamt: 32 (Header) + 4×32 (Deskriptoren) + 1 (Terminator 0x0D) = 161 Bytes → erster Datensatz bei Offset 0xA1.
🧭 Idee: aus Deskriptoren werden Offsets
Der Reader liest erst den Header, dann alle Feld-Deskriptoren bis zum Terminator 0x0D. Aus den Feldlängen werden die Offsets im Satz aufaddiert – damit lässt sich jede dBase-Tabelle generisch zerlegen, ohne pro Tabelle ein eigenes struct zu schreiben.
| Feld | Typ | Länge | Offset | Byte-Bereich |
|---|---|---|---|---|
| deleted | – | 1 | 0 | [0] |
| NAME | C | 20 | 1 | [1 … 20] |
| STREET | C | 25 | 21 | [21 … 45] |
| CITY | C | 18 | 46 | [46 … 63] |
| ZIP | C | 5 | 64 | [64 … 68] |
Satzbreite gesamt: 69 Bytes · Offset-Formel: offset[i] = offset[i−1] + length[i−1]
🖥️ Beispielausgabe
NAME (C,20) = 'Mueller, Anna' STREET (C,25) = 'Hauptstrasse 1' CITY (C,18) = 'Berlin' ZIP (C, 5) = '10115'
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdint.h>#pragma pack(push, 1) /* keine Padding-Bytes: exaktes Dateilayout */typedef struct { /* 32-Byte-Dateikopf */ uint8_t version; uint8_t year, month, day; uint32_t num_records; uint16_t header_size; /* Bytes bis zum 1. Datensatz */ uint16_t record_size; /* Bytes pro Datensatz (inkl. Loeschflag) */ uint8_t reserved[20];} DBF_Header;typedef struct { /* 32-Byte-Feld-Deskriptor */ char name[11]; char type; /* 'C','N','D','L','M' */ uint32_t data_address; uint8_t length; /* Feldlaenge in Bytes */ uint8_t decimal_count; uint8_t reserved[14];} DBF_Field;#pragma pack(pop)int main(int argc, char **argv) { FILE *fp = fopen("ADDRESS.DBF", "rb"); if (!fp) { perror("fopen"); return 1; } /* 1) Dateikopf lesen */ DBF_Header hdr; fread(&hdr, sizeof(hdr), 1, fp); /* 2) Feld-Deskriptoren dynamisch lesen, bis Terminator 0x0D. Aus den Laengen ergeben sich die Feld-Offsets im Satz. */ DBF_Field fields[128]; int field_offset[128]; int nfields = 0; int offset = 1; /* Byte 0 = Loeschflag */ for (;;) { int c = fgetc(fp); if (c == 0x0D || c == EOF) break; /* Ende der Deskriptoren */ ungetc(c, fp); fread(&fields[nfields], sizeof(DBF_Field), 1, fp); field_offset[nfields] = offset; /* Position dieses Feldes */ offset += fields[nfields].length; nfields++; } /* 3) Direktzugriff auf einen Satz per Offset-Rechnung */ long recno = (argc > 1) ? atol(argv[1]) : 1; long pos = hdr.header_size + (recno - 1) * hdr.record_size; fseek(fp, pos, SEEK_SET); uint8_t *rec = malloc(hdr.record_size); fread(rec, hdr.record_size, 1, fp); if (rec[0] == 0x2A) { printf("Satz %ld ist geloescht\n", recno); } /* 4) Felder GENERISCH zerlegen - kein festes struct noetig! */ for (int i = 0; i < nfields; i++) { char buf[256]; int len = fields[i].length; memcpy(buf, rec + field_offset[i], len); buf[len] = '\0'; for (int k = len - 1; k >= 0 && buf[k] == ' '; k--) buf[k] = '\0'; printf("%-11s (%c,%2d) = '%s'\n", fields[i].name, fields[i].type, len, buf); } free(rec); fclose(fp); return 0;}Index in Aktion – Select, Insert, Index & Query
Der NDX-Index ist ein B-Baum. Select zeigt die Suche von der Wurzel zum Datensatz, Insert das Anhängen eines Satzes inkl. Knoten-Split, Index den Aufbau der .NDX-Datei und Query, wie ein SELECT per lex/yacc in Tokens und einen Syntaxbaum zerlegt wird. Geschwindigkeit einstellbar oder Schritt für Schritt.
🌳 NDX B-Tree-Index (Schlüssel: NAME)
🗂️ ADDRESS.DBF – Datensätze
Der Index liefert nur die Satznummer. Damit springt dBase per Offset direkt zum Datensatz – ohne die übrigen Sätze zu lesen.
| recno | Offset | NAME | STREET | CITY | ZIP |
|---|---|---|---|---|---|
| 1 | 0xA1 | Mueller, Anna | Hauptstrasse 1 | Berlin | 10115 |
| 2 | 0xE6 | Schmidt, Bernd | Lindenweg 12 | Hamburg | 20095 |
| 3 | 0x12B | Fischer, Clara | Bahnhofstr. 5 | Muenchen | 80331 |
| 4 | 0x170 | Weber, Dieter | Gartenstr. 8 | Koeln | 50667 |
| 5 | 0x1B5 | Wagner, Emma | Ringstrasse 22 | Frankfurt | 60311 |
| 6 | 0x1FA | Becker, Frank | Seeweg 3 | Stuttgart | 70173 |
| 7 | 0x23F | Hoffmann, Greta | Marktplatz 9 | Dresden | 01067 |
| 8 | 0x284 | Schaefer, Hans | Wiesenweg 4 | Leipzig | 04109 |
| 9 | 0x2C9 | Koch, Ingrid | Talstrasse 17 | Bremen | 28195 |
| 10 | 0x30E | Bauer, Jens | Bergweg 6 | Hannover | 30159 |
| 11 | 0x353 | Richter, Karl | Feldstr. 14 | Nuernberg | 90402 |
| 12 | 0x398 | Klein, Laura | Parkallee 2 | Dortmund | 44135 |