B-tree dan indeks database

 (planetscale.com)
41 poin oleh GN⁺ 2024-09-11 | 1 komentar | Bagikan ke WhatsApp

Apa itu B-tree?

  • B-tree berperan sebagai fondasi bagi banyak perangkat lunak, khususnya sistem manajemen basis data (DBMS)

  • MySQL, Postgres, MongoDB, Dynamo, dan lainnya bergantung pada B-tree untuk melakukan pengambilan data secara efisien melalui indeks

  • Akan dipelajari bagaimana B-tree dan B+tree bekerja, mengapa database menggunakannya untuk indeks, dan mengapa menggunakan UUID sebagai kunci utama bisa menjadi ide yang buruk

  • B-tree menyimpan pasangan data yang dikenal sebagai key dan value dalam struktur yang oleh programmer komputer disebut mirip pohon

  • B-tree terdiri dari node (persegi panjang) dan pointer anak (garis yang menghubungkan node)

  • Node paling atas disebut root node, node pada level paling bawah disebut leaf node, dan semua node lainnya disebut internal node

  • Berikut definisi B-tree:

    • Setiap node menyimpan N pasangan key/value (dengan N lebih besar dari 1 dan kurang dari atau sama dengan K)
    • Setiap internal node memiliki minimal N/2 pasangan key/value (internal node adalah node yang bukan leaf maupun root)
    • Setiap node memiliki N+1 anak
    • Root node memiliki setidaknya satu nilai dan dua anak, kecuali jika itu satu-satunya node
    • Semua leaf berada pada level yang sama

  • Fitur inti lain dari B-tree adalah pengurutan. Di dalam setiap node, elemen dipertahankan dalam urutan tertentu

  • Berkat kemampuan pengurutan ini, pencarian key bisa dilakukan dengan sangat efisien. Pencarian dimulai dari root node lalu:

    1. Periksa apakah key yang dicari ada di dalam node
    2. Jika tidak ada, cari posisi di dalam node tempat key akan disisipkan jika ingin ditambahkan
    3. Pada titik ini, ikuti pointer anak ke level berikutnya dan ulangi prosesnya

  • Dengan cara ini, saat mencari, cukup mengunjungi satu node pada setiap level pohon untuk menemukan satu key

  • B-tree dirancang khusus agar bekerja baik saat menangani data dalam jumlah sangat besar yang juga harus disimpan secara persisten dalam penyimpanan jangka panjang (disk). Alasannya, setiap node menggunakan jumlah byte yang tetap

  • Jumlah nilai yang dapat disimpan tiap node dalam B-tree bergantung pada jumlah byte yang dialokasikan untuk node tersebut dan jumlah byte yang dikonsumsi oleh setiap pasangan key/value

B+tree (dioptimalkan untuk database)

  • B+tree mirip dengan B-tree, tetapi aturan berikut berubah:
    • Pasangan key/value hanya disimpan di leaf node
    • Node non-leaf hanya menyimpan key dan pointer anak yang terkait
  • Ada dua aturan tambahan yang spesifik pada cara MySQL mengimplementasikan B+tree dalam indeksnya:
    • Node non-leaf menyimpan N pointer anak, bukan N+1
    • Semua node juga mencakup pointer "next" dan "previous" sehingga setiap level pohon juga dapat berfungsi sebagai linked list ganda
  • Ada dua alasan mengapa B+tree lebih cocok untuk database:
    1. Karena internal node tidak perlu menyimpan value, lebih banyak key dapat dimasukkan ke setiap internal node. Ini membantu mengurangi kedalaman pohon
    2. Semua value disimpan pada level yang sama dan bisa ditelusuri berurutan melalui linked list pada level terbawah

Cara MySQL menggunakan B+tree

  • MySQL mendukung beberapa storage engine, dan engine yang paling umum digunakan adalah InnoDB, yang sangat bergantung pada B+tree
  • Bahkan, InnoDB sangat bergantung padanya sampai-sampai menyimpan seluruh data tabel dalam B+tree dengan menggunakan primary key tabel sebagai key pohon
  • Setiap kali membuat tabel InnoDB baru, Anda harus menentukan primary key
  • MySQL membuat B+tree untuk setiap tabel baru, dan nilai yang ditetapkan sebagai primary key menjadi key pohon. Valuenya adalah nilai kolom lain pada setiap baris dan hanya disimpan di leaf node
  • Ukuran setiap node dalam B+tree ini secara default ditetapkan ke 16k
  • Setiap kali MySQL perlu mengakses potongan data (key, value, dan sebagainya), MySQL memuat seluruh page terkait (node B+tree) dari disk, meskipun key atau value lain tidak diperlukan
  • Membuat secondary index pada tabel InnoDB juga umum dilakukan. Untuk setiap secondary index, dibangun B+tree persisten tambahan, dengan key berupa kolom yang dipilih pengguna untuk diindeks dan value berupa primary key dari baris terkait

Memilih primary key: penyisipan

  • Karena cara data tabel disusun dalam B+tree berbeda bergantung pada key yang dipilih, pilihan PRIMARY KEY memengaruhi tata letak data seluruh tabel di disk
  • Dua pilihan yang umum digunakan untuk primary key adalah:
    • urutan bilangan bulat (BIGINT UNSIGNED AUTO_INCREMENT dan sejenisnya)
    • UUID (memiliki beberapa versi)
  • Jika menggunakan primary key UUIDv4, akibatnya saat penyisipan:
    1. Node yang dikunjungi untuk penyisipan tidak bisa diprediksi sebelumnya
    2. Leaf node tujuan penyisipan tidak bisa diprediksi
    3. Value dalam leaf tidak terurut
  • Masalah 1 dan 2 muncul karena dalam banyak proses penyisipan, banyak node (page) pada pohon harus dikunjungi. Aktivitas baca dan tulis yang berlebihan ini menyebabkan penurunan performa
  • Jika menggunakan BIGINT UNSIGNED AUTO_INCREMENT sebagai primary key:
    1. Saat menyisipkan value baru, jalurnya selalu mengikuti sisi paling kanan
    2. Leaf hanya ditambahkan di sisi kanan pohon
    3. Pada level leaf, data diurutkan sesuai urutan penyisipannya
  • Karena poin 1 dan 2, banyak penyisipan berurutan akan mengunjungi kembali jalur page yang sama, sehingga permintaan I/O berkurang saat menyisipkan banyak pasangan key/value

Memilih primary key: membaca data secara berurutan

  • Mengambil data berdasarkan urutan waktu adalah hal yang umum dalam database
  • Jika menggunakan UUIDv4 sebagai primary key, urutan value hasil pencarian akan tersebar di beberapa leaf node yang tidak berurutan
  • Saat mencari value yang disisipkan secara berurutan, semua page yang berisi hasil pencarian akan saling berdekatan. Saat mengambil beberapa baris, semuanya bahkan bisa berdekatan dalam satu page yang sama
  • Untuk pola query seperti ini, penggunaan primary key berurutan dapat mengurangi jumlah page yang perlu dibaca

Memilih primary key: ukuran

  • Ukuran primary key juga merupakan pertimbangan penting. Primary key harus selalu:
    1. cukup besar agar tidak habis
    2. cukup kecil agar tidak menggunakan ruang penyimpanan berlebihan
  • Untuk urutan bilangan bulat, tabel yang lebih kecil dapat menggunakan MEDIUMINT (16 juta nilai unik) atau INT (4 miliar nilai unik)
  • Untuk tabel besar, gunakan BIGINT agar aman (sekitar 18 kuintiliun kemungkinan nilai). BIGINT berukuran 64 bit (8 byte)
  • UUID umumnya berukuran 128 bit (16 byte), dua kali lebih besar daripada tipe integer terbesar di MySQL
  • Karena node B+tree berukuran tetap, menggunakan BIGINT memungkinkan lebih banyak key dimasukkan ke tiap node dibanding UUID. Ini menghasilkan pohon yang lebih dangkal dan lookup yang lebih cepat

B+tree, page, dan InnoDB

  • Salah satu keunggulan besar B+tree adalah ukuran node dapat diatur sesuai kebutuhan
  • Di InnoDB, node B+tree umumnya diatur ke 16k, yaitu ukuran InnoDB page
  • Saat memproses query (dan karena itu menelusuri B+tree), InnoDB tidak membaca baris dan kolom satu per satu dari disk. Setiap kali perlu mengakses potongan data, seluruh page terkait dimuat dari disk
  • InnoDB memiliki beberapa teknik untuk mengurangi dampak ini, dan teknik utamanya adalah buffer pool. Buffer pool adalah cache dalam memori untuk InnoDB page yang berada di antara page di disk dan eksekusi query MySQL
  • Saat MySQL perlu membaca sebuah page, MySQL terlebih dulu memeriksa apakah page itu sudah ada di buffer pool. Jika ada, page dibaca dari sana dan operasi disk I/O dilewati. Jika tidak ada, MySQL mencari page tersebut di disk, menambahkannya ke buffer pool, lalu melanjutkan eksekusi query
  • Buffer pool sangat meningkatkan performa query. Tanpa buffer pool, jauh lebih banyak operasi disk I/O harus dilakukan untuk menangani beban kerja query

Situasi lain

  • Di sini fokus utamanya adalah membandingkan key berurutan dengan key acak/UUID, tetapi prinsip-prinsip ini tetap berguna untuk diingat terlepas dari jenis primary key atau secondary key yang sedang dipertimbangkan
  • Misalnya, Anda bisa mempertimbangkan penggunaan timestamp user.created_at sebagai key indeks, yang memiliki karakteristik mirip integer berurutan. Kecuali saat menyisipkan data lama, penyisipan biasanya akan selalu bergerak ke jalur paling kanan
  • Sebaliknya, string seperti user.email_address memiliki karakteristik yang lebih mirip key acak. Pengguna tidak membuat akun berdasarkan urutan alfabet email, sehingga penyisipan terjadi di seluruh bagian B+tree

Kesimpulan

  • Banyak hal telah dibahas tentang B+tree, indeks, dan pemilihan primary key
  • Sekilas semuanya tampak sederhana, tetapi ada perbedaan-perbedaan halus yang perlu dipertimbangkan untuk memaksimalkan performa database
  • Untuk eksperimen lebih lanjut, kunjungi situs web B+tree interaktif

Bacaan terkait

1 komentar

 
GN⁺ 2024-09-11
Komentar Hacker News

  • Menjaga wiki tetap berguna dengan memakai strategi pengelolaan seperti B-Tree

    • Jika landing page menjadi terlalu banyak, pindahkan tautan dan paragraf ke subhalaman
    • Tautan lama yang mirip dipindahkan ke halaman saudara yang sesuai dengan topiknya
    • Pada akhirnya, dokumen lama dipindahkan tiga tingkat ke bawah dari landing page
    • Dokumentasi pada akhirnya bermuara pada masalah pencarian
    • Cara yang bagus untuk menghabiskan Jumat sore dengan produktif

  • Sudah lama mencari hal seperti ini, postingan yang luar biasa

    • Andai ada bagian tentang indeks gabungan

  • Terima kasih atas materi visual yang luar biasa

    • Pernah mengerjakan dukungan pengindeksan BTree+ di atas Aerospike
    • Menghapus key yang kedaluwarsa dari BTree+ adalah tantangan
    • Diputuskan untuk menggabungkan satu cabang level hanya di dalam sibling leaf node pertama
    • Menambahkan sharding di atas BTree+ untuk meningkatkan kecepatan dan mengurangi kontensi lock
    • BTree+ bisa menjadi tidak seimbang selama proses pembersihan
    • Menyediakan fungsi rebuild index untuk menghindari pekerjaan pembersihan tambahan

  • Modal cookie tidak berfungsi di Firefox mobile

    • Harus memungkinkan pengguna mengaturnya lewat browser

  • Sebaiknya jangan memakai kolom UUID sebagai primary key

    • Harus menyalin int 128-bit ke semua sisi relasi
    • Dalam kebanyakan kasus benar-benar acak
    • Untuk relasi tabel internal, sebaiknya gunakan PK bigserial (64-bit), dan gunakan UUID (128-bit) untuk identifier level aplikasi serta natural key
    • Database akan jauh lebih senang

  • Materi pembelajaran yang luar biasa

    • Demo interaktif seperti ini sangat membantu

  • Jika blok disk dan node B-Tree berukuran 16k, dan key, value, serta child pointer semuanya 8 bit, maka per node bisa menyimpan 682 key/value dan 683 child pointer

    • Pohon tiga level dapat menyimpan lebih dari 300 juta pasangan key/value
    • Seharusnya 8 byte per elemen

  • Artikel yang sangat bagus

    • InnoDB menyebut penyimpanan data di dalam B-tree itu sendiri sebagai clustered index
    • MyISAM adalah indeks non-clustered
    • Oracle dan lainnya memungkinkan kita memilih

  • Bertanya apa arti v0, v1, ...v10 pada grafik

    • Penasaran apakah itu merujuk ke halaman yang berbeda

  • Visualisasi interaktif yang indah

    • Kelas tertinggi dari sisi edukasi dan popularisasi