Bottleneck Sequential Access pada Format DBF di Browser

Format dBase (DBF) menyimpan data secara sekuensial dengan fixed-length record setelah block header. Parser DBF standar berbasis JavaScript umumnya membaca keseluruhan array buffer, lalu melakukan parsing teks/field satu per satu ke JavaScript heap memory sebelum melakukan operasi filtering (Array.prototype.filter atau Array.prototype.find).

Ketika dataset mencapai ratusan ribu baris (misal: 200.000 record dengan ukuran 150 byte per row = ~30 MB data biner mentah), pendekatan sequential parsing memicu dua masalah utama:

  • GC Pressure: Membuat jutaan objek JavaScript kecil menyebabkan Garbage Collector browser terhenti (stop-the-world pauses).
  • Kompleksitas O(N): Query WHERE field = 'X' memerlukan sequential read dari record 0 hingga N-1, membaca byte disk/buffer yang tidak relevan.

Arsitektur Pointer Indexing: Mengakses Binary DBF via Offset

DBF format Level III / IV memiliki struktur header biner tetap:

  • Bytes 4-7: Record count (32-bit unsigned little-endian integer).
  • Bytes 8-9: Header size / data offset awal (16-bit unsigned little-endian integer).
  • Bytes 10-11: Record size (16-bit unsigned little-endian integer).

Alih-alih mendeserialisasi seluruh baris, kita hanya perlu membaca primary/search key secara linier satu kali untuk membangun index map (atau B-Tree). Nilai index bukan merupakan salinan objek row, melainkan integer byte offset dari record tersebut di dalam ArrayBuffer.

Implementasi: Indexing Off-Heap Pointer Menggunakan Map/B-Tree Sederhana

Berikut adalah implementasi JavaScript minimal untuk mengekstrak field target dan menyimpan pointer byte offset secara langsung menggunakan DataView:

class DbfIndexedReader {
  constructor(arrayBuffer, keyFieldOffset, keyFieldLength) {
    this.buffer = arrayBuffer;
    this.view = new DataView(arrayBuffer);
    this.keyFieldOffset = keyFieldOffset;
    this.keyFieldLength = keyFieldLength;
    this.decoder = new TextDecoder("ascii");

    this.recordCount = this.view.getUint32(4, true);
    this.headerSize = this.view.getUint16(8, true);
    this.recordSize = this.view.getUint16(10, true);

    // Menggunakan Map terurut / sorted pairs untuk simulasi indeks O(1) ke O(log N)
    this.index = new Map();
  }

  buildIndex() {
    const totalBytes = this.buffer.byteLength;
    for (let i = 0; i < this.recordCount; i++) {
      const recordStart = this.headerSize + (i * this.recordSize);
      if (recordStart + this.recordSize > totalBytes) break;

      // Cek deletion flag: byte 0x2A (*) menandakan baris dihapus, 0x20 spasi aktif
      const deleteFlag = this.view.getUint8(recordStart);
      if (deleteFlag === 0x2A) continue;

      const fieldStart = recordStart + this.keyFieldOffset;
      const rawKeyBytes = new Uint8Array(this.buffer, fieldStart, this.keyFieldLength);
      const key = this.decoder.decode(rawKeyBytes).trim();

      // ponytail: Map cukup untuk pencarian unik; gunakan B-Tree sejati jika butuh range-query (BETWEEN / > / <)
      this.index.set(key, recordStart);
    }
  }

  findByKey(key) {
    const recordOffset = this.index.get(key);
    if (recordOffset === undefined) return null;
    return this.readRecord(recordOffset);
  }

  readRecord(offset) {
    const recordSlice = new Uint8Array(this.buffer, offset, this.recordSize);
    return this.decoder.decode(recordSlice);
  }
}

Komparasi Performa: Full-Table Scan vs Index Lookup

Tabel komparasi karakteristik eksekusi query pada file DBF 200.000 record di V8 runtime:

  • Full-Table Scan: Kompleksitas pencarian O(N). Menghabiskan waktu CPU linier pada setiap query (misal: 15–40 ms per query bergantung posisi record). Memory heap meningkat proporsional jika baris di-deserialisasi ke string/objek.
  • B-Tree / Map Pointer Index: Kompleksitas pencarian O(1) atau O(log N). Waktu eksekusi drop ke sub-milidetik (<0.05 ms per lookup). Alokasi memori hanya sebesar key string dan integer pointer byte offset.

Verifikasi dan Validasi Benchmark

Jalankan uji latensi menggunakan API bawaan performance.now() tanpa framework external untuk mengukur direct execution time:

// Inisialisasi mock DBF buffer sederhana untuk pengujian
const RECORD_COUNT = 100000;
const RECORD_SIZE = 32;
const HEADER_SIZE = 64;
const buffer = new ArrayBuffer(HEADER_SIZE + (RECORD_COUNT * RECORD_SIZE));
const view = new DataView(buffer);

view.setUint32(4, RECORD_COUNT, true);
view.setUint16(8, HEADER_SIZE, true);
view.setUint16(10, RECORD_SIZE, true);

// Isi mock key baris terakhir
const targetKey = "ID_99999";
const targetPos = HEADER_SIZE + ((RECORD_COUNT - 1) * RECORD_SIZE);
view.setUint8(targetPos, 0x20); // Not deleted
new Uint8Array(buffer, targetPos + 1, targetKey.length).set(new TextEncoder().encode(targetKey));

const reader = new DbfIndexedReader(buffer, 1, 8);
reader.buildIndex();

// Benchmark Index Lookup
const t0 = performance.now();
const resultIndexed = reader.findByKey(targetKey);
const t1 = performance.now();

console.assert(resultIndexed !== null, "Record harus ditemukan");
console.log(`Index Lookup Time: ${(t1 - t0).toFixed(4)} ms`);

Catatan: Jika data DBF melebihi kapasitas memori browser (>500MB), hindari menahan seluruh ArrayBuffer di memori. Gunakan File API File.slice() dikombinasikan dengan B-Tree index berbasis chunk offset disk untuk lazy reading.