1.2 Definisi
B-Tree

B-Tree
adalah sebuah
m-ary balanced search tree
khusus yang digunakan dalam basis data karena strukturnya memungkinkan data yang disimpan untuk disisipi, dihapus, dan diambil dengan jaminan proses dengan waktu terburuk, di mana setiap simpulnya terdiri dari (
m
/2) sampai
m
buah simpul anak, di mana
m
> 1 merupakan bilangan bulat.
m
adalah orde. Akar pohon
B-tree
paling sedikit memiliki 2 simpul anak. Ini adalah struktur yang baik jika pohon digunakan pada memori yang lambat, karena ketinggian dan jumlah akses dapat diperkecil dengan mengambil bilangan
m
yang besar.
Balanced tree
atau pohon seimbang adalah pohon dimana tidak ada simpul daun yang lebih panjang terhadap daun yang lain.
Search tree
adalah pohon dimana setiap subpohon dari sebuah simpul mempunyai kunci lebih kecil dari subpohon kanan simpul tersebut. Kunci dalam sebuah simpul secara konsep berada di antara subpohon-subpohon dan lebih besar dari kunci di subpohon kiri simpul dan lebih kecil dari kunci di subpohon kanan simpul. Sebuah
B-Tree
didesain untuk digunakan pada
disk.

Disk
hanya dapat membaca dan menulis blok data ukuran tetap (berukuran besar) sekaligus. Sebuah
B-tree
menyimpan banyak kunci di setap simpulnya sehingga (1) sebuah
disk
dapat mengakses banyak kunci, dan (2) faktor cabang pohon sangat tinggi (dalam prakteknya lebih besar dari
1000) sehingga pohon dengan ketinggian kecil dapat menyimpan kunci dalam jumlah yang sangat besar, yang dapat diakses hanya dengan beberapa operasi.