Menggunakan file teks untuk penyimpanan indeks

Pada posting sebelumnya, saya menggunakan database relasional untuk menyimpan inverted index. Namun atas arahan supervisor, saya akhirnya menggunakan file teks saja (flat file).

Salah satu alasannya karena ternyata database relasional yang digunakan tidak dimanfaatkan fitur “relasional”-nya alias hanya difungsikan sebagai penyimpanan record saja, selain itu juga karena data bersifat statis tanpa ada perubahan. Maka lebih baik jika bisa menggunakan database nonrelasional (jenis NoSQL) agar lebih efisien. Namun karena tidak ada sistem NoSQL yang simpel untuk data saya yang terbilang kecil, maka saya putuskan menggunakan file teks saja untuk menyimpan datanya.

Sebenarnya konsepnya sama, yang berbeda hanya saat menulis indeks. Kalau yang menggunakan database kita menulis ke tabel, maka dengan file teks kita menulis daftar term dan posting list ke file teks.

Index:

term1|1,5,7,10,15
term2|6,9,10,15
term3|3,4
...

Namun kalau hanya menulis ke file teks saja tanpa teknik tertentu, maka akan cukup repot saat proses pencarian atau pemrosesan query nantinya. Kalau dengan database mudah, karena kita cukup menggunakan perintah SELECT ... WHERE term = 'AAA'. Namun bagaimana kalau data kita ternyata ada di file teks?

Ada satu teknik yang disarankan, yaitu memecah antara daftar term dan posting list. Jadi file indeks kita terdiri dari 2 file, yaitu daftar term dan posting list.

Terms:

term1|0
term2|12
term3|22
...

Posting:

1,5,7,10,15
6,9,10,15
3,4
...

Kenapa perlu dipisahkan? Karena daftar posting bisa sangat besar ukurannya, dan kita tidak perlu me-load file besar itu seluruhnya. Sebaliknya, daftar term biasanya ukurannya tidak terlalu besar, jadi kalaupun kita load seluruhnya ke memori tidak menjadi masalah. Daftar term hendaknya terurut, agar saat kita mencari term tertentu bisa kita efisienkan, misalnya dengan binary search. Kalau saya sendiri menggunakan hash table karena term-nya tidak terlalu banyak.

Nah, angka di sebelah term adalah offset. Misalkan term2 offset-nya 12, artinya term2 memiliki daftar posting pada file posting list mulai byte ke-12 sampai akhir baris. Jadi kita cukup membaca byte ke-12 sampai akhir baris saja tanpa harus membaca seluruh file posting list.

Implementasi saya dengan PHP bisa menggunakan fungsi fseek untuk membaca file langsung pada byte sekian.

Dengan mekanisme pemisahan seperti ini, pencarian daftar posting yang sesuai untuk term tertentu dapat dilakukan dengan cepat. Dengan binary search dapat dilakukan pada O(log n), sedangkan dengan hash table pada O(1).

Dan sebenarnya, kita sedang membuat DBMS kita sendiri, karena cara membaca terindeks seperti ini juga digunakan oleh DBMS untuk mencari record dengan cepat :)