B-Tree Serialization Encoding

Raymond Kelvin Nando — B-Tree Serialization Encoding merupakan metode pengkodean terstruktur untuk merepresentasikan sebuah B-Tree ke dalam format linear sehingga dapat disimpan, ditransmisikan, atau direkonstruksi kembali tanpa kehilangan struktur internalnya. Encoding ini penting dalam sistem basis data, indexing, penyimpanan on-disk, serta mekanisme transfer struktur data kompleks antar proses atau antar mesin. B-Tree Serialization Encoding memfokuskan diri pada representasi node, child pointer, nilai kunci, serta metadata tree seperti derajat dan jumlah kunci dalam setiap node.

Pengertian B-Tree Serialization Encoding

B-Tree Serialization Encoding adalah proses mengubah struktur pohon B-Tree menjadi bentuk serial yang dapat dibaca secara sekuensial, baik dalam format biner maupun teks. Proses ini mencakup penulisan informasi node sebagai blok data yang berisi jumlah kunci, derajat, array kunci, pointer anak, serta penanda apakah node tersebut adalah leaf.

Tujuan utama encoding ini:

• Menyimpan B-Tree ke dalam file secara efisien.
• Melakukan transfer antar proses atau jaringan.
• Memungkinkan rekonstruksi pohon secara deterministik.
• Menjaga konsistensi indeks pada database seperti SQLite, MySQL (variasi), dan sistem file.

Encoding B-Tree harus mempertahankan urutan kunci, struktur anak, dan kemampuan navigasi yang sama seperti saat berada dalam memori.

Sejarah Perkembangan B-Tree Serialization Encoding

B-Tree sebagai struktur data diperkenalkan oleh Rudolf Bayer dan Edward McCreight pada tahun 1970-an. Sejak itu, B-Tree digunakan secara luas dalam sistem penyimpanan dan basis data. Kebutuhan untuk menyimpan indeks dalam media disk mendorong lahirnya teknik encoding yang memetakan node ke dalam blok penyimpanan, biasanya diselaraskan dengan ukuran block storage (misalnya 4 KB).

Dengan berkembangnya database modern seperti Berkeley DB, PostgreSQL, dan sistem file seperti ReiserFS, metode serialization B-Tree berkembang menjadi lebih kompleks, termasuk optimisasi:

• On-disk layout yang fixed-length.
• Buffering dan caching node.
• Penggunaan pointer logis (offset).
• Kompresi prefix kunci.

Di era distribusi data modern (misalnya pada sistem log-structured atau penyimpanan terdistribusi), serialization B-Tree juga digunakan untuk snapshot, checkpoint, dan transport antar node dalam cluster.

Prinsip Dasar dan Metode B-Tree Serialization Encoding

Encoding B-Tree biasanya mengikuti struktur node internal yang terdiri dari metadata diikuti dengan data kunci dan pointer anak.

1. Format Node

Node umumnya berisi:

• Flag leaf (0 atau 1).
• Jumlah kunci (n).
• Array kunci dengan panjang n.
• Pointer anak sebanyak n+1 untuk node non-leaf.
• Metadata tambahan seperti derajat tree.

Contoh struktur:
LeafFlag
KeyCount
Keys[n]
Children[n+1]

2. Urutan Serialisasi

Traversing node dilakukan dengan pola tertentu:

• Preorder traversal sering dipakai: encode node → encode children.
• Alternatif: breadth-first untuk kemudahan rekonstruksi.
• On-disk format biasanya mengikuti fixed-size block.

3. Representasi Kunci

Kunci dapat disimpan dalam:

• Integer 32/64 bit.
• String dengan panjang variabel.
• Fixed-length key.
• Kompresi prefix bila kunci berurutan.

4. Pointer Anak

Pointer anak dapat direpresentasikan sebagai:

• Offset file.
• Index node dalam array serial.
• Handle atau ID node.
• Null pointer (untuk leaf).

5. Metadata Penting

Beberapa encoding menyimpan metadata berikut:

• Derajat B-Tree (t).
• Panjang blok.
• Versi.
• Checksum (opsional).

6. Dekode / Rekonstruksi

Decoder membaca stream secara linear, membangun node, lalu menautkan pointer anak sesuai urutan.

7. Binary Encoding vs Text Encoding

Binary encoding: lebih ringkas, cepat, fixed layout.
Text encoding: lebih mudah dibaca manusia (contoh: JSON, XML).

8. Konsistensi

Untuk menjamin integritas pada disk:

• CRC atau checksum per node.
• Pointer anak harus valid offset.
• Node harus aligned dengan block disk.

Contoh Input → Output B-Tree Serialization Encoding

Contoh 1: B-Tree derajat 2

B-Tree:
[10 | 20]
/ | \
[5] [12|18] [25]

Encoding preorder:

Node 1 (root):
LeafFlag=0
KeyCount=2
Keys: 10 20
Children pointer: 1 2 3

Node 2:
LeafFlag=1
KeyCount=1
Keys: 5

Node 3:
LeafFlag=1
KeyCount=2
Keys: 12 18

Node 4:
LeafFlag=1
KeyCount=1
Keys: 25

Representasi biner (sederhana):
00 02 0A 14 00 00 00 01 00 00 00 02 00 00 00 03
01 01 05
01 02 0C 12
01 01 19

Contoh 2: Text Encoding

{
“leaf”: false,
“keys”: [10,20],
“children”: [
{“leaf”: true, “keys”:[5]},
{“leaf”: true, “keys”:[12,18]},
{“leaf”: true, “keys”:[25]}
]
}

Contoh 3: Encoding string key

KeyCount=3
Keys: apple banana cherry
Format:
06 apple 06 banana 06 cherry

Contoh 4: Offset-based encoding

Node offset list:
Root @0x0000
Child1 @0x0100
Child2 @0x0200
Child3 @0x0300

Output biner berisi offset pointer.

Contoh 5: Kompresi prefix

Keys: application, apply, appoint
Stored:
app | lication | ly | oint

Contoh 6: Breadth-first serialization

Queue: root → children → grandchildren

Output linear:
[10,20] [5] [12,18] [25]

Contoh 7: Snapshot encoding

Serialisasi seluruh B-Tree untuk backup database:
Header → Node Count → Nodes → Checksum

Kelebihan & Kekurangan B-Tree Serialization Encoding

Kelebihan:

• Efisien untuk penyimpanan on-disk.
• Mempertahankan struktur B-Tree secara lengkap.
• Cocok untuk database dan indexing.
• Mendukung traversing dan rekonstruksi cepat.
• Kompatibel dengan teknik optimisasi seperti prefix compression.
• Format dapat diadaptasi sesuai kebutuhan sistem.
• Mendukung snapshot dan transfer antar sistem.

Kekurangan:

• Membutuhkan metadata tambahan, sehingga ukuran bertambah.
• Pointer anak harus dikelola dengan ketat.
• Kesalahan kecil dapat merusak seluruh tree.
• Lebih kompleks dibanding serialisasi struktur linear.
• Perlu versi skema agar backward-compatible.
• Kurang ramah debugging jika format biner.
• Fragmentasi block pada media penyimpanan bisa terjadi.

Referensi

• Bayer, R., & McCreight, E. (1972). Organization and Maintenance of Large Ordered Indexes.
• Comer, D. (1979). The Ubiquitous B-Tree.
• Silberschatz, A., Korth, H., & Sudarshan, S. (2020). Database System Concepts.
• Zaitsev, D. (2018). B-Tree Storage Structures in Databases.
• Oracle Corp. (2023). B-Tree Index Architecture Documentation.