Bagaimana basis data menyimpan nilai kunci indeks (pada disk) untuk bidang panjang variabel?

Konteks

Pertanyaan ini berkaitan dengan rincian implementasi tingkat rendah dari indeks di kedua sistem database SQL dan NoSQL. Struktur aktual indeks (B + tree, hash, SSTable, dll.) Tidak relevan karena pertanyaan terkait secara khusus dengan kunci yang disimpan di dalam satu simpul dari salah satu implementasi tersebut.

Latar Belakang

Dalam database SQL (mis. MySQL) dan NoSQL (CouchDB, MongoDB, dll.), Ketika Anda membangun indeks pada kolom atau bidang data dokumen JSON, apa yang sebenarnya menyebabkan database Anda lakukan adalah membuat dasarnya daftar yang diurutkan dari semua nilai-nilai tersebut bersama dengan file diimbangi ke file data utama di mana catatan yang berkaitan dengan nilai itu hidup.

(Demi kesederhanaan, saya mungkin melambaikan tangan rincian esoterik lainnya dari impl tertentu)

Contoh SQL Klasik Sederhana

Pertimbangkan tabel SQL standar yang memiliki kunci primer int 32-bit sederhana yang kita buat indeksnya, kita akan berakhir dengan indeks pada-disk kunci integer yang diurutkan dan dikaitkan dengan offset 64-bit ke dalam file data di mana catatan hidup, misalnya:

id   | offset
--------------
1    | 1375
2    | 1413
3    | 1786

Representasi on-disk dari kunci dalam indeks terlihat seperti ini:

[4-bytes][8-bytes] --> 12 bytes for each indexed value

Berpegang teguh pada aturan standar tentang mengoptimalkan disk I / O dengan sistem file dan sistem database, misalkan Anda menyimpan kunci dalam blok 4KB pada disk, yang berarti:

4096 bytes / 12 bytes per key = 341 keys per block

Mengabaikan keseluruhan struktur indeks (B + tree, hash, daftar yang diurutkan, dll.) Kita membaca dan menulis blok 341 kunci sekaligus ke dalam memori dan kembali ke disk sesuai kebutuhan.

Contoh Permintaan

Menggunakan informasi dari bagian sebelumnya, katakanlah kueri masuk untuk "id = 2", pencarian indeks DB klasik berjalan sebagai berikut:

1. Baca akar indeks (dalam hal ini, 1 blok)
2. Biner-cari blok diurutkan untuk menemukan kunci
3. Dapatkan offset data file dari nilai
4. Cari catatan di file data menggunakan offset
5. Kembalikan data ke pemanggil

Penyiapan Pertanyaan ...

Ok, ini pertanyaannya ...

Langkah # 2 adalah bagian terpenting yang memungkinkan kueri ini dieksekusi dalam waktu O (logn) ... informasinya harus disortir, TETAPI Anda harus mampu melintasi daftar dengan cara cepat-sortir ... selengkapnya khusus, Anda harus dapat melompat ke offset yang ditentukan dengan baik untuk membaca nilai kunci indeks pada posisi itu.

Setelah membaca di blok, Anda harus dapat melompat ke posisi 170 segera, membaca nilai kunci dan melihat apakah yang Anda cari adalah GT atau LT posisi itu (dan seterusnya dan seterusnya ...)

Satu-satunya cara Anda dapat melompati data dalam blok seperti itu adalah jika ukuran nilai kunci semuanya terdefinisi dengan baik, seperti contoh kami di atas (4-byte kemudian 8-byte per kunci).

PERTANYAAN

Ok, jadi di sinilah saya terjebak dengan desain indeks yang efisien ... untuk kolom varchar di database SQL atau lebih khusus, bidang formulir yang benar-benar bebas dalam database dokumen seperti CouchDB atau NoSQL, di mana bidang apa pun yang ingin Anda indeks dapat berupa apa saja panjang bagaimana Anda menerapkan nilai-nilai kunci yang ada di dalam blok struktur indeks tempat Anda membangun indeks?

Sebagai contoh, katakanlah Anda menggunakan penghitung berurutan untuk ID di CouchDB dan Anda mengindeks tweet ... Anda akan memiliki nilai yang berubah dari "1" menjadi "100.000.000.000" setelah beberapa bulan.

Katakanlah Anda membangun indeks pada basis data pada hari 1, ketika hanya ada 4 tweet di database, CouchDB mungkin tergoda untuk menggunakan konstruk berikut untuk nilai-nilai kunci di dalam blok indeks:

[1-byte][8-bytes] <-- 9 bytes
4096 / 9 = 455 keys per block

Pada titik tertentu, ini terputus dan Anda perlu sejumlah byte untuk menyimpan nilai kunci Anda dalam indeks.

Intinya bahkan lebih mencolok jika Anda memutuskan untuk mengindeks bidang yang benar-benar panjang variabel seperti "tweet_message" atau sesuatu.

Dengan kunci itu sendiri yang benar-benar panjang variabel, dan database tidak memiliki cara untuk menebak dengan cerdas beberapa "ukuran kunci maksimum" ketika indeks dibuat dan diperbarui, bagaimana sebenarnya kunci-kunci ini disimpan di dalam blok yang mewakili segmen indeks dalam database ini. ?

Jelas jika kunci Anda berukuran variabel dan Anda membaca di blok kunci, Anda tidak hanya tidak tahu berapa banyak kunci yang sebenarnya ada di blok, tetapi Anda juga tidak tahu bagaimana cara melompat ke tengah daftar untuk melakukan biner. cari pada mereka.

Di sinilah saya mendapatkan semua tersandung.

Dengan bidang yang diketik statis dalam database SQL klasik (seperti bool, int, char, dll.) Saya mengerti indeks hanya dapat menentukan sebelumnya panjang kunci dan tetap padanya ... tetapi di dunia ini menyimpan data dokumen, saya bingung bagaimana mereka memodelkan data ini pada disk secara efisien sehingga masih dapat dipindai dalam waktu O (logn) dan akan menghargai klarifikasi apa pun di sini.

Harap beri tahu saya jika diperlukan klarifikasi!

Perbarui (Jawaban Greg)

Silakan lihat komentar saya terlampir pada jawaban Greg. Setelah seminggu melakukan penelitian lebih lanjut, saya pikir dia benar-benar menemukan saran yang sangat sederhana dan berkinerja bahwa dalam praktiknya adalah mati-mudah untuk diterapkan dan digunakan sambil memberikan kemenangan kinerja besar pada menghindari deserialisasi nilai-nilai kunci yang tidak Anda pedulikan.

Saya telah melihat ke dalam 3 implementasi DBMS yang terpisah (CouchDB, kivaloo dan InnoDB) dan semuanya menangani masalah ini dengan membatalkan deserialisasi seluruh blok ke dalam struktur data internal sebelum mencari nilai di dalam lingkungan eksekusi mereka (erlang / C).

Ini yang menurut saya sangat brilian tentang saran Greg; ukuran blok normal 2048 biasanya akan memiliki 50 atau kurang offset, menghasilkan blok angka yang sangat kecil yang perlu dibaca.

Perbarui (Potensi Kerugian untuk Saran Greg)

Untuk melanjutkan dialog ini dengan diri saya sendiri, saya menyadari kerugian berikut ini ...

1. Jika setiap "blok" diarahkan dengan data offset, Anda tidak bisa membiarkan ukuran blok disesuaikan dalam konfigurasi nanti karena Anda mungkin akan membaca data yang tidak dimulai dengan header dengan benar atau blok yang berisi beberapa tajuk.

2. Jika Anda mengindeks nilai-nilai kunci yang sangat besar (misalnya seseorang mencoba mengindeks kolom char (8192) atau gumpalan (8192)) adalah mungkin bahwa kunci tidak cocok dalam satu blok tunggal dan perlu diluap melintasi dua blok berdampingan . Ini berarti blok pertama Anda akan memiliki header ofset dan blok kedua akan segera dimulai dengan data kunci.

Solusi untuk semua ini adalah memiliki ukuran blok basis data tetap yang tidak dapat disesuaikan dan mengembangkan struktur data blok header di sekitarnya ... misalnya, Anda memperbaiki semua ukuran blok menjadi 4KB (biasanya tetap yang paling optimal) dan menulis yang sangat kecil blok header yang menyertakan "tipe blok" di awal. Jika ini adalah blok normal, maka segera setelah header blok harus menjadi header offset. Jika ini merupakan tipe "overflow", maka segera setelah header blok adalah data kunci mentah.

Pembaruan (Potensi sisi atas yang mengagumkan)

Setelah blok dibaca sebagai serangkaian byte dan offset diterjemahkan; secara teknis Anda bisa menyandikan kunci yang Anda cari ke byte mentah dan kemudian melakukan perbandingan langsung pada aliran byte.

Setelah kunci yang Anda cari ditemukan, pointer dapat diterjemahkan dan diikuti.

Efek samping lain yang luar biasa dari ide Greg! Potensi untuk optimasi waktu CPU di sini cukup besar sehingga pengaturan ukuran blok tetap mungkin layak dilakukan hanya untuk mendapatkan semua ini.

Anda dapat menyimpan indeks Anda sebagai daftar offset ukuran tetap ke dalam blok yang berisi data kunci Anda. Sebagai contoh:

+--------------+
| 3            | number of entries
+--------------+
| 16           | offset of first key data
+--------------+
| 24           | offset of second key data
+--------------+
| 39           | offset of third key data
+--------------+
| key one |
+----------------+
| key number two |
+-----------------------+
| this is the third key |
+-----------------------+

(well, data kunci akan diurutkan dalam contoh nyata, tetapi Anda mendapatkan idenya).

Perhatikan bahwa ini tidak selalu mencerminkan bagaimana blok indeks sebenarnya dibangun di basis data apa pun. Ini hanyalah contoh bagaimana Anda bisa mengatur blok data indeks di mana data kunci panjang variabel.