Perbedaan utama: Di komputer, pohon biner adalah struktur data pohon yang menyimpan data, dan memungkinkan pengguna untuk mengakses, mencari, menyisipkan, dan menghapus data pada waktu algoritmik. Perbedaan antara pohon B dan B + adalah bahwa, dalam pohon-B, kunci dan data dapat disimpan di simpul internal dan daun, sedangkan di pohon B +, data dan kunci hanya dapat disimpan di simpul daun .
Binary tree adalah pohon pencarian seimbang yang dirancang untuk bekerja dengan baik pada perangkat penyimpanan sekunder akses langsung seperti disk magnetik. Rudolf Bayer dan Ed McCreight menemukan konsep pohon-B.
B-tree adalah pohon pencarian biner umum, di mana setiap node dapat memiliki lebih dari dua anak. Setiap node internal dalam B-tree berisi sejumlah kunci. Kunci-kunci ini memisahkan nilai-nilai, dan selanjutnya membentuk sub-pohon. Node internal dalam B-tree dapat memiliki jumlah variabel child node, yang disusun dalam rentang yang ditentukan sebelumnya. Pada saat setiap data dimasukkan atau dihapus dari setiap node, ada perubahan dalam jumlah node anak. Untuk mempertahankan rentang yang telah ditentukan, node internal dapat bergabung atau dibagi. Dalam B-tree, rentang node anak diizinkan, karena rentang yang telah ditentukan harus dipertahankan.
Pohon-B tidak perlu diseimbangkan berulang kali tidak seperti pohon pencarian mandiri lainnya. Simpul di pohon-pohon ini tidak selalu penuh; karenanya, ruang yang dikonsumsi tidak perlu di pohon-pohon ini mengarah pada pemborosan ruang. Hanya batas bawah dan atas pada jumlah node anak yang biasanya diperbaiki untuk implementasi tertentu. Sebagai contoh, dalam pohon 2-3 B (sering disebut sebagai pohon 2-3), setiap simpul internal mungkin hanya memiliki 2 atau 3 simpul anak.
Selain itu, B-tree dioptimalkan untuk sistem yang membaca dan menulis blok data yang besar. Ini biasanya digunakan dalam database dan sistem file. Di pohon B, semua node disimpan pada kedalaman balancing yang sama dari node root. Kedalaman ini meningkat perlahan seiring dengan meningkatnya jumlah elemen; ini menghasilkan semua node daun menjadi satu simpul lagi yang lebih jauh dari root. Lebih lanjut, B-tree lebih menguntungkan jika dibandingkan dengan implementasi lain dalam hal waktu yang dibutuhkan untuk mengakses data.
Pohon B + adalah pohon n-array dengan simpul, yang terdiri dari sejumlah besar anak per simpul. Akar dapat berupa daun atau simpul yang berisi lebih dari dua anak. Pohon B + terdiri dari akar, simpul internal dan daun.
Pohon B + sama dengan pohon B; satu-satunya perbedaan adalah bahwa, di pohon B + ada tingkat tambahan yang ditambahkan di bagian bawah dengan daun yang terhubung. Juga, tidak seperti pohon B, setiap simpul dalam pohon B + hanya berisi kunci dan bukan pasangan nilai kunci.
Selain itu, faktor penyeimbang atau urutan pohon B + mengukur kapasitas node internal dalam sebuah pohon, yaitu jumlah node yang dapat mereka miliki. Jumlah aktual anak-anak untuk sebuah node terbatas untuk node internal. Namun, root adalah pengecualian karena diperbolehkan memiliki lebih dari dua anak. Misalnya, jika urutan pohon B + adalah 7, setiap simpul internal (kecuali untuk root) mungkin memiliki antara 4 dan 7 anak; sementara root mungkin memiliki antara 2 dan 7. Nilai utama dari pohon B + adalah dalam menyimpan data untuk pengambilan efisien dalam konteks penyimpanan berorientasi blok dan dalam sistem file tertentu.
Nilai utama dari pohon B + adalah dalam menyimpan dan memelihara data, sehingga data tidak hilang. Pendekatan ini terutama diterapkan dalam konteks penyimpanan berorientasi blok dan dalam beberapa sistem file tertentu. Daun, yang merupakan blok paling bawah indeks, dari pohon B + sering dihubungkan satu sama lain dalam daftar tertaut; karenanya ini membuat rentang kueri atau iterasi yang dipesan melalui blok menjadi lebih sederhana dan lebih efisien. Selanjutnya, faktor ruang tidak terbuang di pohon B +. Pohon B + menyediakan format struktur data perumahan yang efisien, yang membuatnya mudah diakses dan disimpan. Pohon B + sangat berguna sebagai indeks sistem basis data, di mana data biasanya berada pada disk.
Perbandingan antara B Tree dan B + Tree:
B Tree | B + Tree | |
Deskripsi web pendek | AB tree adalah struktur organisasi untuk penyimpanan dan pengambilan informasi dalam bentuk pohon di mana semua node terminal berada pada jarak yang sama dari basis, dan semua node non-terminal memiliki antara n dan 2 n sub-pohon atau pointer (di mana n adalah bilangan bulat). | B + tree adalah pohon n-array dengan variabel tetapi seringkali banyak anak per node. Pohon B + terdiri dari akar, simpul internal dan daun. Akar dapat berupa daun atau simpul dengan dua anak atau lebih. |
Juga dikenal sebagai | Pohon seimbang. | B ditambah pohon. |
Ruang | Di) | Di) |
Pencarian | O (log n) | O (log b n) |
Memasukkan | O (log n) | O (log b n) |
Menghapus | O (log n) | O (log b n) |
Penyimpanan | Di pohon B, kunci pencarian dan data disimpan di internal atau leaf node. | Dalam pohon B +, data disimpan hanya dalam node daun. |
Data | Node daun dari tiga pointer toko ke catatan daripada catatan yang sebenarnya. | Simpul daun pohon menyimpan catatan aktual daripada petunjuk ke catatan. |
Ruang | Pohon-pohon ini membuang-buang ruang | Di sana pohon tidak menyia-nyiakan ruang. |
Fungsi simpul daun | Di pohon B, simpul daun tidak bisa menyimpan menggunakan daftar tertaut. | Di pohon B +, data simpul daun disusun dalam daftar tertaut berurutan. |
Mencari | Di sini, pencarian menjadi sulit di B-tree karena data tidak dapat ditemukan di node leaf. | Di sini, mencari data apa pun di pohon B + sangat mudah karena semua data ditemukan dalam simpul daun. |
Aksesibilitas pencarian | Di sini, di pohon B pencarian tidak semudah dibandingkan dengan pohon B +. | Di sini, di pohon B + pencarian menjadi mudah. |
Kunci redundan | Mereka tidak menyimpan kunci pencarian yang berlebihan. | Mereka menyimpan kunci pencarian yang berlebihan. |
Aplikasi | Mereka adalah versi yang lebih lama dan tidak terlalu menguntungkan dibandingkan dengan pohon B +. | Banyak pelaksana sistem basis data lebih menyukai kesederhanaan struktur pohon B +. |
