Dalam ilmu komputer, B-Tree adalah struktur data pohon yang membuat data diurutkan dan memungkinkan pencarian, akses sekuensial, sisipan, dan penghapusan dalam waktu diamortisasi logaritmik. B-Tree adalah generalisasi dari sebuah pohon pencarian biner dalam sebuah node dapat memiliki lebih dari dua anak, seperti self-balancing pohon pencarian biner, B-Tree dioptimalkan untuk sistem yang membaca dan menulis blok data yang besar. Hal ini umumnya digunakan dalam database dan filesystem.
Pengantar
Dalam B-pohon, internal (non-daun) node dapat memiliki sejumlah variabel node anak dalam beberapa rentang yang telah ditentukan. Ketika data dimasukkan atau dihapus dari node, jumlah node anak atas perubahan. Dalam rangka mempertahankan kisaran yang telah ditentukan, node internal dapat bergabung atau split. Karena berbagai node anak diizinkan, B-Tree tidak perlu menyeimbangkan kembali sesering lainnya yang self-balancing pohon pencarian, tetapi mungkin limbah beberapa ruang, karena node tidak sepenuhnya penuh. Batas bawah dan atas pada jumlah node anak biasanya tetap untuk implementasi tertentu. Sebagai contoh, dalam 2-3 B-Tree (sering hanya disebut sebagai pohon 2-3), setiap node internal mungkin hanya 2 atau 3 node anak.
Setiap node internal B-Tree akan berisi sejumlah tombol. Biasanya, jumlah kunci yang dipilih bervariasi antara d dan 2d. Dalam prakteknya, kunci mengambil ruang paling dalam di node. Faktor 2 akan menjamin bahwa node dapat dibagi atau dikombinasikan. Jika simpul internal memiliki tombol 2d, kemudian menambahkan kunci ke node yang dapat dicapai dengan memisahkan node kunci 2d menjadi dua node tombol d dan menambahkan kunci ke node induk. Setiap node split memiliki jumlah minimum yang diperlukan kunci. Demikian pula, jika node internal dan tetangganya masing-masing memiliki tombol d, maka kunci dapat dihapus dari node internal dengan menggabungkan dengan tetangganya. Menghapus kunci akan membuat simpul internal memiliki d - 1 kunci; bergabung dengan tetangga akan menambahkan kunci d ditambah satu kunci yang lebih diturunkan dari orangtua tetangga. Hasilnya adalah simpul seluruhnya penuh kunci 2d.
Jumlah cabang (atau node anak) dari sebuah node akan menjadi salah satu lebih dari jumlah kunci yang disimpan dalam node. Dalam B-Tree 2-3, node internal akan menyimpan salah satu kunci (dengan dua node anak) atau dua tombol (dengan tiga node anak). Sebuah B-Tree kadang-kadang digambarkan dengan parameter (d + 1) - (2d + 1) atau hanya dengan perintah percabangan tertinggi, (2d + 1).
Sebuah B-Tree disimpan seimbang dengan mensyaratkan bahwa semua node daun pada kedalaman yang sama. Kedalaman ini akan meningkat perlahan-lahan sebagai elemen yang ditambahkan ke pohon, namun peningkatan kedalaman keseluruhan adalah jarang, dan hasil di semua node daun yang satu node yang lebih jauh dari akar.
B-Tree memiliki keunggulan substansial atas implementasi alternatif ketika waktu akses node jauh melebihi waktu akses dalam node [penjelasan lebih lanjut diperlukan]. Hal ini biasanya terjadi ketika node dalam penyimpanan sekunder seperti disk drive. Dengan memaksimalkan jumlah node anak dalam setiap simpul internal, ketinggian pohon berkurang dan jumlah node akses yang mahal berkurang. Selain itu, menyeimbangkan pohon semakin jarang terjadi. Jumlah maksimum node anak tergantung pada informasi yang harus disimpan untuk setiap node anak dan ukuran blok disk penuh atau ukuran analog dalam penyimpanan sekunder. Sementara 2-3 B-Tree lebih mudah untuk menjelaskan, praktis B-Tree menggunakan penyimpanan sekunder ingin sejumlah besar node anak untuk meningkatkan kinerja.
Istilah B-Tree mungkin mengacu pada desain tertentu atau mungkin mengacu pada kelas umum desain. Dalam arti sempit, B-Tree toko kunci dalam node internal, tetapi tidak perlu menyimpan kunci-kunci dalam catatan di daun. Kelas umum mencakup variasi seperti pohon B +-pohon dan B *-.
Dalam B +-tree, salinan kunci disimpan dalam node internal, tombol dan catatan disimpan dalam daun, di samping itu, simpul daun mungkin termasuk pointer ke node daun berikutnya untuk mempercepat akses sekuensial.
B *- tree node internal yang lebih saldo tetangga untuk menjaga node internal lebih padat. Sebagai contoh, node non-akar B-Tree harus setidaknya setengah penuh, tetapi non- root node dari pohon B *- harus setidaknya dua pertiga penuh.
Dihitung B-Tree toko, dengan masing-masing pointer dalam pohon, jumlah node dalam subtree bawah pointer. Hal ini memungkinkan pencarian cepat untuk catatan dalam rangka kunci, atau menghitung jumlah record antara dua catatan, dan berbagai operasi lain yang terkait.
Etimologi
Rudolf Bayer dan Ed McCreight menemukan B-Tree saat bekerja di Boeing Research Labs pada tahun 1971 (Bayer & McCreight 1972), tetapi mereka tidak menjelaskan apa. Douglas Comer menjelaskan:
Asal "B-Tree" tidak pernah dijelaskan oleh penulis. Sebagaimana akan kita lihat, "seimbang", "luas," atau "lebat" mungkin berlaku. Lain menyarankan bahwa "B" singkatan untuk Boeing. Karena kontribusi, bagaimanapun, tampaknya tepat untuk berpikir dari B-Tree sebagai "Bayer"-Tree.
Donald Knuth berspekulasi pada etimologi B-Tree Mei, 1980 kuliah pada "kelas kuliah CS144C tentang penyimpanan disk dan B-Tree" topik, menunjukkan "B" mungkin berasal dari Boeing atau dari nama Bayer. Knuth video ceramah dari Stanford
Masalah database
Waktu untuk mencari file diurutkan
Biasanya, pemilahan dan mencari algoritma telah ditandai dengan jumlah operasi perbandingan yang harus dilakukan dengan menggunakan notasi pesanan. Sebuah pencarian biner tabel diurutkan dengan catatan N, misalnya, dapat dilakukan dalam O (log2N) perbandingan. Jika tabel telah 1.000.000 catatan, maka catatan tertentu bisa ditemukan dengan sekitar 20 perbandingan: log21, 000,000 = 19,931 ....
Database yang besar secara historis telah disimpan pada disk drive. Waktu untuk membaca catatan pada hard disk dapat mendominasi waktu yang dibutuhkan untuk membandingkan tombol sekali catatan tersedia. Waktu untuk membaca catatan dari sebuah disk drive melibatkan waktu mencari dan penundaan rotasi. Waktu mencari mungkin 0-20 milidetik atau lebih, dan rata-rata rotasi penundaan sekitar setengah periode rotasi. Untuk drive 7200 RPM, periode rotasi 8,33 milidetik. Untuk drive seperti ST3500320NS Seagate, jalur-ke-track mencari waktu adalah 0,8 milidetik dan membaca rata-rata seek time adalah 8.5 milidetik. Untuk mempermudah, asumsikan membaca dari disk membutuhkan waktu sekitar 10 milidetik.
Maka, waktu untuk mencari satu catatan dari satu juta akan mengambil 20 kali dibaca disk 10 milidetik per disk dibaca, yang adalah 0,2 detik.
Waktu tidak akan seburuk itu karena catatan individu dikelompokkan bersama dalam sebuah blok disk. Sebuah blok disk dapat 16 kilobyte. Jika setiap record adalah 160 byte, kemudian 100 catatan bisa disimpan di setiap blok. Disk membaca waktu di atas sebenarnya untuk seluruh blok. Setelah disk kepala dalam posisi, satu atau lebih blok disk dapat dibaca dengan sedikit delay. Dengan 100 record per blok, 6 terakhir ini perbandingan tidak perlu melakukan disk apapun membaca-perbandingan semua dalam blok disk yang terakhir dibacanya.
Untuk mempercepat pencarian lebih lanjut, 13 sampai 14 pertama perbandingan (yang masing-masing membutuhkan akses disk) harus dipercepat.
Rudolf Bayer dan Ed McCreight menemukan B-Tree saat bekerja di Boeing Research Labs pada tahun 1971 (Bayer & McCreight 1972), tetapi mereka tidak menjelaskan apa. Douglas Comer menjelaskan:
Asal "B-Tree" tidak pernah dijelaskan oleh penulis. Sebagaimana akan kita lihat, "seimbang", "luas," atau "lebat" mungkin berlaku. Lain menyarankan bahwa "B" singkatan untuk Boeing. Karena kontribusi, bagaimanapun, tampaknya tepat untuk berpikir dari B-Tree sebagai "Bayer"-Tree.
Donald Knuth berspekulasi pada etimologi B-Tree Mei, 1980 kuliah pada "kelas kuliah CS144C tentang penyimpanan disk dan B-Tree" topik, menunjukkan "B" mungkin berasal dari Boeing atau dari nama Bayer. Knuth video ceramah dari Stanford
Masalah database
Waktu untuk mencari file diurutkan
Biasanya, pemilahan dan mencari algoritma telah ditandai dengan jumlah operasi perbandingan yang harus dilakukan dengan menggunakan notasi pesanan. Sebuah pencarian biner tabel diurutkan dengan catatan N, misalnya, dapat dilakukan dalam O (log2N) perbandingan. Jika tabel telah 1.000.000 catatan, maka catatan tertentu bisa ditemukan dengan sekitar 20 perbandingan: log21, 000,000 = 19,931 ....
Database yang besar secara historis telah disimpan pada disk drive. Waktu untuk membaca catatan pada hard disk dapat mendominasi waktu yang dibutuhkan untuk membandingkan tombol sekali catatan tersedia. Waktu untuk membaca catatan dari sebuah disk drive melibatkan waktu mencari dan penundaan rotasi. Waktu mencari mungkin 0-20 milidetik atau lebih, dan rata-rata rotasi penundaan sekitar setengah periode rotasi. Untuk drive 7200 RPM, periode rotasi 8,33 milidetik. Untuk drive seperti ST3500320NS Seagate, jalur-ke-track mencari waktu adalah 0,8 milidetik dan membaca rata-rata seek time adalah 8.5 milidetik. Untuk mempermudah, asumsikan membaca dari disk membutuhkan waktu sekitar 10 milidetik.
Maka, waktu untuk mencari satu catatan dari satu juta akan mengambil 20 kali dibaca disk 10 milidetik per disk dibaca, yang adalah 0,2 detik.
Waktu tidak akan seburuk itu karena catatan individu dikelompokkan bersama dalam sebuah blok disk. Sebuah blok disk dapat 16 kilobyte. Jika setiap record adalah 160 byte, kemudian 100 catatan bisa disimpan di setiap blok. Disk membaca waktu di atas sebenarnya untuk seluruh blok. Setelah disk kepala dalam posisi, satu atau lebih blok disk dapat dibaca dengan sedikit delay. Dengan 100 record per blok, 6 terakhir ini perbandingan tidak perlu melakukan disk apapun membaca-perbandingan semua dalam blok disk yang terakhir dibacanya.
Untuk mempercepat pencarian lebih lanjut, 13 sampai 14 pertama perbandingan (yang masing-masing membutuhkan akses disk) harus dipercepat.
Indeks Sebuah kecepatan pencarian
Sebuah peningkatan yang signifikan dapat dibuat dengan indeks. Dalam contoh di atas, disk awal membaca mempersempit rentang pencarian dengan faktor dua. Yang dapat ditingkatkan secara substansial dengan membuat indeks tambahan yang berisi rekaman pertama di setiap blok disk (kadang-kadang disebut indeks jarang). Indeks ini akan menjadi tambahan 1% dari ukuran database asli, tetapi dapat dicari lebih cepat. Menemukan sebuah entri dalam indeks tambahan akan memberitahu kita yang menghambat untuk mencari di database utama, setelah mencari indeks tambahan, kita akan harus mencari hanya satu blok utama database-dengan biaya dari satu disk lebih banyak membaca. Indeks akan terus 10.000 entri, sehingga akan mengambil paling banyak 14 perbandingan. Seperti database utama, 6 atau lebih terakhir perbandingan dalam indeks aux akan di blok disk yang sama. Indeks bisa dicari di sekitar 8 disk membaca, dan catatan yang diinginkan dapat diakses di 9 disk berbunyi.
Trik menciptakan indeks tambahan dapat diulang untuk membuat indeks tambahan ke indeks tambahan. Itu akan membuat indeks aux-aux yang akan hanya perlu 100 entri dan akan cocok dalam satu blok disk.
Alih-alih membaca blok disk 14 untuk menemukan catatan yang diinginkan, kita hanya perlu membaca 3 blok. Membaca dan mencari blok (dan hanya) pertama dari aux-aux indeks mengidentifikasi blok yang relevan dalam aux-indeks. Membaca dan mencari bahwa aux-indeks blok mengidentifikasi blok yang relevan dalam database utama. Alih-alih 150 milidetik, kita hanya perlu 30 milidetik untuk mendapatkan catatan.
Indeks-indeks tambahan telah mengubah masalah pencarian dari pencarian biner yang membutuhkan disk sekitar log2N membaca satu hanya membutuhkan disk logbN membaca di mana b adalah faktor menghalangi (jumlah entri per blok: b = 100 entri per blok; logb1, 000,000 = 3 kali dibaca).
Dalam prakteknya, jika database utama sedang sering dicari, indeks aux-aux dan banyak dari indeks aux mungkin berada dalam disk cache, sehingga mereka tidak akan dikenakan disk membaca.
Jika database tidak berubah, maka kompilasi indeks sederhana untuk dilakukan, dan indeks tidak perlu diubah. Jika ada perubahan, maka mengelola database dan indeks menjadi lebih rumit.
Menghapus catatan dari database tidak menyebabkan banyak kesulitan. Index dapat tetap sama, dan merekam hanya dapat ditandai sebagai dihapus. Database tetap dalam rangka diurutkan. Jika ada banyak penghapusan, maka pencarian dan penyimpanan menjadi kurang efisien.
Sisipan adalah bencana dalam file sekuensial diurutkan karena ruangan untuk catatan dimasukkan harus dilakukan. Memasukkan record sebelum record pertama dalam file membutuhkan pergeseran semua catatan bawah satu. Operasi semacam itu adalah terlalu mahal untuk menjadi praktis.
Trik adalah untuk meninggalkan beberapa ruang berbaring sekitar yang akan digunakan untuk insersi. Daripada padat menyimpan semua catatan dalam blok, blok dapat memiliki beberapa ruang bebas untuk memungkinkan untuk insersi berikutnya. Mereka catatan akan ditandai seolah-olah mereka "dihapus" catatan.
Sekarang, baik penyisipan dan penghapusan yang cepat asalkan ruang yang tersedia di blok. Jika suatu penyisipan tidak akan muat di blok, maka beberapa ruang kosong pada beberapa blok di dekatnya harus ditemukan dan indeks tambahan disesuaikan. Harapannya cukup ruang di dekatnya bahwa banyak blok tidak perlu untuk ditata kembali. Atau, beberapa out-of-urutan blok disk dapat digunakan.
B-Tree menggunakan semua ide di atas. Itu membuat catatan dalam rangka diurutkan sehingga mereka dapat secara berurutan dilalui. Ini menggunakan indeks hirarkis untuk meminimalkan jumlah disk membaca. Indeks elegan disesuaikan dengan algoritma rekursif. B-Tree menggunakan blok sebagian penuh untuk mempercepat penyisipan dan penghapusan. Selain itu, B-pohon meminimalkan limbah dengan memastikan node interior minimal 1 / 2 penuh. Sebuah B-Tree dapat menangani jumlah sewenang-wenang insersi dan penghapusan.
Terminologi yang digunakan untuk B-Tree tidak konsisten dalam literatur:
Sayangnya, literatur tentang B-pohon tidak seragam dalam penggunaan istilah-istilah yang berhubungan dengan B-Tree.
Bayer & McCreight (1972), Comer (1979), dan lain-lain menentukan urutan B-Treesebagai jumlah minimum kunci dalam sebuah node non-root. Folk & Zoellick (1992) menunjukkan bahwa terminologi ambigu karena jumlah maksimum kunci tidak jelas. Suatu perintah 3 B-pohon mungkin memegang maksimal 6 kunci atau maksimal 7 kunci. Knuth (1993b) menghindari masalah dengan mendefinisikan perintah untuk menjadi nomor maksimum anak (yang merupakan salah satu lebih dari jumlah maksimum kunci).
Daun Istilah ini juga tidak konsisten. Bayer & McCreight (1972) dianggap sebagai tingkat daun menjadi tingkat terendah kunci, tetapi Knuth (1993b) dianggap tingkat daun menjadi satu tingkat di bawah tombol terendah. Ada banyak pilihan implementasi yang tepat. Dalam beberapa desain, daun dapat memegang rekor seluruh data; dalam desain lain, daun hanya dapat memegang pointer ke record data. Pilihan-pilihan yang tidak mendasar bagi gagasan sebuah B-Tree.
Ada juga pilihan menguntungkan seperti menggunakan variabel k untuk mewakili jumlah anak-anak ketika k bisa bingung dengan jumlah kunci.
Untuk mempermudah, penulis yang paling menganggap ada sejumlah tetap kunci yang cocok dalam sebuah node. Asumsi dasar adalah ukuran kunci adalah tetap dan ukuran node adalah tetap. Dalam prakteknya, panjang variabel kunci dapat digunakan.
Sebuah peningkatan yang signifikan dapat dibuat dengan indeks. Dalam contoh di atas, disk awal membaca mempersempit rentang pencarian dengan faktor dua. Yang dapat ditingkatkan secara substansial dengan membuat indeks tambahan yang berisi rekaman pertama di setiap blok disk (kadang-kadang disebut indeks jarang). Indeks ini akan menjadi tambahan 1% dari ukuran database asli, tetapi dapat dicari lebih cepat. Menemukan sebuah entri dalam indeks tambahan akan memberitahu kita yang menghambat untuk mencari di database utama, setelah mencari indeks tambahan, kita akan harus mencari hanya satu blok utama database-dengan biaya dari satu disk lebih banyak membaca. Indeks akan terus 10.000 entri, sehingga akan mengambil paling banyak 14 perbandingan. Seperti database utama, 6 atau lebih terakhir perbandingan dalam indeks aux akan di blok disk yang sama. Indeks bisa dicari di sekitar 8 disk membaca, dan catatan yang diinginkan dapat diakses di 9 disk berbunyi.
Trik menciptakan indeks tambahan dapat diulang untuk membuat indeks tambahan ke indeks tambahan. Itu akan membuat indeks aux-aux yang akan hanya perlu 100 entri dan akan cocok dalam satu blok disk.
Alih-alih membaca blok disk 14 untuk menemukan catatan yang diinginkan, kita hanya perlu membaca 3 blok. Membaca dan mencari blok (dan hanya) pertama dari aux-aux indeks mengidentifikasi blok yang relevan dalam aux-indeks. Membaca dan mencari bahwa aux-indeks blok mengidentifikasi blok yang relevan dalam database utama. Alih-alih 150 milidetik, kita hanya perlu 30 milidetik untuk mendapatkan catatan.
Indeks-indeks tambahan telah mengubah masalah pencarian dari pencarian biner yang membutuhkan disk sekitar log2N membaca satu hanya membutuhkan disk logbN membaca di mana b adalah faktor menghalangi (jumlah entri per blok: b = 100 entri per blok; logb1, 000,000 = 3 kali dibaca).
Dalam prakteknya, jika database utama sedang sering dicari, indeks aux-aux dan banyak dari indeks aux mungkin berada dalam disk cache, sehingga mereka tidak akan dikenakan disk membaca.
Jika database tidak berubah, maka kompilasi indeks sederhana untuk dilakukan, dan indeks tidak perlu diubah. Jika ada perubahan, maka mengelola database dan indeks menjadi lebih rumit.
Menghapus catatan dari database tidak menyebabkan banyak kesulitan. Index dapat tetap sama, dan merekam hanya dapat ditandai sebagai dihapus. Database tetap dalam rangka diurutkan. Jika ada banyak penghapusan, maka pencarian dan penyimpanan menjadi kurang efisien.
Sisipan adalah bencana dalam file sekuensial diurutkan karena ruangan untuk catatan dimasukkan harus dilakukan. Memasukkan record sebelum record pertama dalam file membutuhkan pergeseran semua catatan bawah satu. Operasi semacam itu adalah terlalu mahal untuk menjadi praktis.
Trik adalah untuk meninggalkan beberapa ruang berbaring sekitar yang akan digunakan untuk insersi. Daripada padat menyimpan semua catatan dalam blok, blok dapat memiliki beberapa ruang bebas untuk memungkinkan untuk insersi berikutnya. Mereka catatan akan ditandai seolah-olah mereka "dihapus" catatan.
Sekarang, baik penyisipan dan penghapusan yang cepat asalkan ruang yang tersedia di blok. Jika suatu penyisipan tidak akan muat di blok, maka beberapa ruang kosong pada beberapa blok di dekatnya harus ditemukan dan indeks tambahan disesuaikan. Harapannya cukup ruang di dekatnya bahwa banyak blok tidak perlu untuk ditata kembali. Atau, beberapa out-of-urutan blok disk dapat digunakan.
B-Tree menggunakan semua ide di atas. Itu membuat catatan dalam rangka diurutkan sehingga mereka dapat secara berurutan dilalui. Ini menggunakan indeks hirarkis untuk meminimalkan jumlah disk membaca. Indeks elegan disesuaikan dengan algoritma rekursif. B-Tree menggunakan blok sebagian penuh untuk mempercepat penyisipan dan penghapusan. Selain itu, B-pohon meminimalkan limbah dengan memastikan node interior minimal 1 / 2 penuh. Sebuah B-Tree dapat menangani jumlah sewenang-wenang insersi dan penghapusan.
Terminologi yang digunakan untuk B-Tree tidak konsisten dalam literatur:
Sayangnya, literatur tentang B-pohon tidak seragam dalam penggunaan istilah-istilah yang berhubungan dengan B-Tree.
Bayer & McCreight (1972), Comer (1979), dan lain-lain menentukan urutan B-Treesebagai jumlah minimum kunci dalam sebuah node non-root. Folk & Zoellick (1992) menunjukkan bahwa terminologi ambigu karena jumlah maksimum kunci tidak jelas. Suatu perintah 3 B-pohon mungkin memegang maksimal 6 kunci atau maksimal 7 kunci. Knuth (1993b) menghindari masalah dengan mendefinisikan perintah untuk menjadi nomor maksimum anak (yang merupakan salah satu lebih dari jumlah maksimum kunci).
Daun Istilah ini juga tidak konsisten. Bayer & McCreight (1972) dianggap sebagai tingkat daun menjadi tingkat terendah kunci, tetapi Knuth (1993b) dianggap tingkat daun menjadi satu tingkat di bawah tombol terendah. Ada banyak pilihan implementasi yang tepat. Dalam beberapa desain, daun dapat memegang rekor seluruh data; dalam desain lain, daun hanya dapat memegang pointer ke record data. Pilihan-pilihan yang tidak mendasar bagi gagasan sebuah B-Tree.
Ada juga pilihan menguntungkan seperti menggunakan variabel k untuk mewakili jumlah anak-anak ketika k bisa bingung dengan jumlah kunci.
Untuk mempermudah, penulis yang paling menganggap ada sejumlah tetap kunci yang cocok dalam sebuah node. Asumsi dasar adalah ukuran kunci adalah tetap dan ukuran node adalah tetap. Dalam prakteknya, panjang variabel kunci dapat digunakan.
Definisi
Menurut definisi Knuth, B-Tree order m (jumlah maksimum anak-anak untuk setiap node) adalah pohon yang memenuhi sifat-sifat sebagai berikut:
Setiap node memiliki pada anak-anak yang paling m.
Setiap node (kecuali root) memiliki setidaknya m / 2 anak-anak.
Akar setidaknya memiliki dua anak jika bukan simpul daun.
Semua daun muncul dalam tingkat yang sama, dan membawa informasi.
Sebuah node non-daun dengan anak-anak mengandung ke k-1 tombol.
Elemen setiap node internal bertindak sebagai pemisahan nilai-nilai yang membagi sub pohon nya. Sebagai contoh, jika sebuah simpul internal memiliki node anak tiga (atau sub pohon) maka harus memiliki nilai pemisahan dua atau elemen a1 dan a2. Semua nilai dalam subtree paling kiri akan kurang dari a1, semua nilai dalam subtree tengah akan antara a1 dan a2, dan semua nilai dalam subtree paling kanan akan lebih besar dari a2.
Node internal di B-Tree - node yang tidak node daun - biasanya direpresentasikan sebagai himpunan terurut dari elemen dan pointer anak. Setiap simpul internal berisi maksimal anak-anak U dan - selain akar - minimal anak L. Untuk semua node internal selain akar, jumlah elemen adalah salah satu kurang dari jumlah pointer anak; jumlah elemen adalah antara L-1 dan U-1. U nomor harus baik 2L atau 2L-1, dengan demikian setiap node internal setidaknya setengah penuh. Hubungan antara U dan L menyiratkan bahwa dua setengah penuh node dapat bergabung untuk membuat node hukum, dan satu simpul penuh dapat dibagi menjadi dua node hukum (jika ada ruang untuk mendorong satu elemen menjadi orangtua). Properti ini memungkinkan untuk menghapus dan memasukkan nilai-nilai baru ke dalam pohon-B dan menyesuaikan pohon untuk melestarikan properti B-Tree.
Node daun memiliki batasan yang sama pada jumlah elemen, tetapi tidak memiliki anak, dan tidak ada pointer anak.
Simpul akar masih memiliki batas atas jumlah anak, tetapi tidak memiliki batas bawah. Sebagai contoh, ketika ada kurang dari L-1 elemen dalam seluruh pohon, akar akan menjadi node hanya di pohon, dan akan tidak punya anak sama sekali.
Sebuah B-Tree kedalaman n +1 dapat menampung sekitar kali U item sebanyak B-Tree mendalam, tetapi biaya pencarian, insert, dan delete tumbuh dengan kedalaman pohon. Seperti halnya pohon seimbang, biaya tumbuh jauh lebih lambat dibandingkan jumlah elemen.
Beberapa nilai toko seimbang pohon hanya pada node daun, dan memiliki berbagai jenis node untuk node daun dan node internal. B-Tree menjaga nilai-nilai dalam setiap node di pohon, dan dapat menggunakan struktur yang sama untuk semua node. Namun, karena node daun tidak pernah memiliki anak, struktur khusus untuk simpul daun dalam B-Tree akan meningkatkan kinerja.
Ketinggian kasus terbaik dari B-Tree adalah:
\ Log m/n. \
Ketinggian kasus terburuk B-Tree adalah:
\ Log m / 2n \
di mana m adalah jumlah maksimum node anak dapat memiliki.
Peringatan: pembahasan di bawah ini menggunakan "unsur", "nilai", "kunci", "pemisah", dan "nilai pemisahan" berarti dasarnya hal yang sama. Istilah yang tidak jelas. Ada beberapa masalah halus pada akar dan daun.
Pencarian mirip dengan mencari sebuah pohon pencarian biner. Mulai dari akar, pohon rekursif melintasi dari atas ke bawah. Pada setiap tingkat, cari memilih pointer anak (subtree) yang pemisahan nilai-nilai di kedua sisi nilai pencarian.
Pencarian biner biasanya (tetapi tidak selalu) digunakan dalam node untuk menemukan nilai-nilai pemisahan dan pohon anak bunga.
Menurut definisi Knuth, B-Tree order m (jumlah maksimum anak-anak untuk setiap node) adalah pohon yang memenuhi sifat-sifat sebagai berikut:
Setiap node memiliki pada anak-anak yang paling m.
Setiap node (kecuali root) memiliki setidaknya m / 2 anak-anak.
Akar setidaknya memiliki dua anak jika bukan simpul daun.
Semua daun muncul dalam tingkat yang sama, dan membawa informasi.
Sebuah node non-daun dengan anak-anak mengandung ke k-1 tombol.
Elemen setiap node internal bertindak sebagai pemisahan nilai-nilai yang membagi sub pohon nya. Sebagai contoh, jika sebuah simpul internal memiliki node anak tiga (atau sub pohon) maka harus memiliki nilai pemisahan dua atau elemen a1 dan a2. Semua nilai dalam subtree paling kiri akan kurang dari a1, semua nilai dalam subtree tengah akan antara a1 dan a2, dan semua nilai dalam subtree paling kanan akan lebih besar dari a2.
Node internal di B-Tree - node yang tidak node daun - biasanya direpresentasikan sebagai himpunan terurut dari elemen dan pointer anak. Setiap simpul internal berisi maksimal anak-anak U dan - selain akar - minimal anak L. Untuk semua node internal selain akar, jumlah elemen adalah salah satu kurang dari jumlah pointer anak; jumlah elemen adalah antara L-1 dan U-1. U nomor harus baik 2L atau 2L-1, dengan demikian setiap node internal setidaknya setengah penuh. Hubungan antara U dan L menyiratkan bahwa dua setengah penuh node dapat bergabung untuk membuat node hukum, dan satu simpul penuh dapat dibagi menjadi dua node hukum (jika ada ruang untuk mendorong satu elemen menjadi orangtua). Properti ini memungkinkan untuk menghapus dan memasukkan nilai-nilai baru ke dalam pohon-B dan menyesuaikan pohon untuk melestarikan properti B-Tree.
Node daun memiliki batasan yang sama pada jumlah elemen, tetapi tidak memiliki anak, dan tidak ada pointer anak.
Simpul akar masih memiliki batas atas jumlah anak, tetapi tidak memiliki batas bawah. Sebagai contoh, ketika ada kurang dari L-1 elemen dalam seluruh pohon, akar akan menjadi node hanya di pohon, dan akan tidak punya anak sama sekali.
Sebuah B-Tree kedalaman n +1 dapat menampung sekitar kali U item sebanyak B-Tree mendalam, tetapi biaya pencarian, insert, dan delete tumbuh dengan kedalaman pohon. Seperti halnya pohon seimbang, biaya tumbuh jauh lebih lambat dibandingkan jumlah elemen.
Beberapa nilai toko seimbang pohon hanya pada node daun, dan memiliki berbagai jenis node untuk node daun dan node internal. B-Tree menjaga nilai-nilai dalam setiap node di pohon, dan dapat menggunakan struktur yang sama untuk semua node. Namun, karena node daun tidak pernah memiliki anak, struktur khusus untuk simpul daun dalam B-Tree akan meningkatkan kinerja.
Ketinggian kasus terbaik dari B-Tree adalah:
\ Log m/n. \
Ketinggian kasus terburuk B-Tree adalah:
\ Log m / 2n \
di mana m adalah jumlah maksimum node anak dapat memiliki.
Peringatan: pembahasan di bawah ini menggunakan "unsur", "nilai", "kunci", "pemisah", dan "nilai pemisahan" berarti dasarnya hal yang sama. Istilah yang tidak jelas. Ada beberapa masalah halus pada akar dan daun.
Pencarian mirip dengan mencari sebuah pohon pencarian biner. Mulai dari akar, pohon rekursif melintasi dari atas ke bawah. Pada setiap tingkat, cari memilih pointer anak (subtree) yang pemisahan nilai-nilai di kedua sisi nilai pencarian.
Pencarian biner biasanya (tetapi tidak selalu) digunakan dalam node untuk menemukan nilai-nilai pemisahan dan pohon anak bunga.
Insertion
Semua sisipan mulai pada simpul daun. Untuk menyisipkan elemen baru
Cari pohon untuk mencari simpul daun di mana elemen baru harus ditambahkan. Masukkan elemen baru ke dalam node dengan langkah-langkah berikut:
Jika node berisi kurang dari jumlah maksimum elemen hukum, maka ada ruang untuk unsur baru. Masukkan unsur baru dalam node, menjaga elemen node memerintahkan.
Jika node sudah penuh, merata membaginya menjadi dua node sehingga:
Sebuah median tunggal dipilih dari antara elemen daun dan unsur baru.
Nilai kurang dari median diletakkan di node kiri baru dan nilai-nilai lebih besar dari median diletakkan di node kanan baru, dengan bertindak median sebagai nilai pemisahan.
Nilai pemisahan dimasukkan ke dalam induk node, yang dapat menyebabkan itu untuk dibagi, dan seterusnya. Jika node tidak memiliki orangtua (yaitu, node adalah akar), membuat akar baru di atas node ini (meningkatkan ketinggian pohon).
Jika membelah berjalan sepanjang jalan sampai ke akar, itu menciptakan akar baru dengan nilai pemisah tunggal dan dua anak, yang mengapa batas bawah pada ukuran node internal tidak berlaku untuk root. Jumlah maksimum elemen per node adalah U-1. Ketika sebuah node dibagi, satu elemen bergerak ke orangtua, tetapi salah satu elemen ditambahkan. Jadi, harus dimungkinkan untuk membagi jumlah maksimal U-1 elemen menjadi dua node hukum. Jika nomor ini adalah ganjil, maka U = 2L dan salah satu node baru berisi (U-2) / 2 = L-1 elemen, dan karenanya adalah node hukum, dan yang lain berisi satu elemen lagi, dan karena itu adalah hukum juga. Jika U-1 adalah genap, maka U = 2L-1, jadi ada 2L-2 elemen dalam node. Setengah dari jumlah ini adalah L-1, yang merupakan jumlah minimum elemen diperbolehkan per node.
Sebuah algoritma ditingkatkan mendukung single pass bawah pohon dari akar ke simpul di mana penyisipan akan berlangsung, membelah setiap node penuh ditemui di jalan. Hal ini untuk mencegah kebutuhan untuk mengingat node induk ke dalam memori, yang mungkin mahal jika node pada penyimpanan sekunder. Namun, untuk menggunakan algoritma ditingkatkan, kita harus mampu mengirim satu elemen orang tua dan membagi U-2 yang tersisa elemen menjadi dua node hukum, tanpa menambahkan elemen baru. Hal ini membutuhkan U = 2L daripada U = 2L-1, yang menjelaskan mengapa beberapa buku menerapkan persyaratan ini dalam mendefinisikan B-Tree.
Cari pohon untuk mencari simpul daun di mana elemen baru harus ditambahkan. Masukkan elemen baru ke dalam node dengan langkah-langkah berikut:
Jika node berisi kurang dari jumlah maksimum elemen hukum, maka ada ruang untuk unsur baru. Masukkan unsur baru dalam node, menjaga elemen node memerintahkan.
Jika node sudah penuh, merata membaginya menjadi dua node sehingga:
Sebuah median tunggal dipilih dari antara elemen daun dan unsur baru.
Nilai kurang dari median diletakkan di node kiri baru dan nilai-nilai lebih besar dari median diletakkan di node kanan baru, dengan bertindak median sebagai nilai pemisahan.
Nilai pemisahan dimasukkan ke dalam induk node, yang dapat menyebabkan itu untuk dibagi, dan seterusnya. Jika node tidak memiliki orangtua (yaitu, node adalah akar), membuat akar baru di atas node ini (meningkatkan ketinggian pohon).
Jika membelah berjalan sepanjang jalan sampai ke akar, itu menciptakan akar baru dengan nilai pemisah tunggal dan dua anak, yang mengapa batas bawah pada ukuran node internal tidak berlaku untuk root. Jumlah maksimum elemen per node adalah U-1. Ketika sebuah node dibagi, satu elemen bergerak ke orangtua, tetapi salah satu elemen ditambahkan. Jadi, harus dimungkinkan untuk membagi jumlah maksimal U-1 elemen menjadi dua node hukum. Jika nomor ini adalah ganjil, maka U = 2L dan salah satu node baru berisi (U-2) / 2 = L-1 elemen, dan karenanya adalah node hukum, dan yang lain berisi satu elemen lagi, dan karena itu adalah hukum juga. Jika U-1 adalah genap, maka U = 2L-1, jadi ada 2L-2 elemen dalam node. Setengah dari jumlah ini adalah L-1, yang merupakan jumlah minimum elemen diperbolehkan per node.
Sebuah algoritma ditingkatkan mendukung single pass bawah pohon dari akar ke simpul di mana penyisipan akan berlangsung, membelah setiap node penuh ditemui di jalan. Hal ini untuk mencegah kebutuhan untuk mengingat node induk ke dalam memori, yang mungkin mahal jika node pada penyimpanan sekunder. Namun, untuk menggunakan algoritma ditingkatkan, kita harus mampu mengirim satu elemen orang tua dan membagi U-2 yang tersisa elemen menjadi dua node hukum, tanpa menambahkan elemen baru. Hal ini membutuhkan U = 2L daripada U = 2L-1, yang menjelaskan mengapa beberapa buku menerapkan persyaratan ini dalam mendefinisikan B-Tree.
Penghapusan
Ada dua strategi populer untuk penghapusan dari B-Tree.cari dan menghapus item, maka restrukturisasi pohon untuk mendapatkan kembali invariants nya
atau
melakukan single pass bawah pohon, tapi sebelum masuk (mengunjungi) node, merestrukturisasi pohon sehingga setelah kunci untuk dihapus ditemui, dapat dihapus tanpa memicu perlu untuk setiap restrukturisasi lanjut
Algoritma di bawah ini menggunakan strategi mantan.
Ada dua kasus khusus untuk dipertimbangkan ketika menghapus sebuah elemen:
elemen dalam sebuah node internal dapat pemisah untuk node anaknya
menghapus elemen dapat menempatkan simpul di bawah jumlah minimum elemen dan anak-anak.
Masing-masing kasus akan dibahas dalam rangka.
Penghapusan dari simpul daun
Mencari nilai untuk menghapus.
Jika nilai dalam node daun, itu hanya dapat dihapus dari node,
Jika underflow terjadi, periksa baik saudara mentransfer tombol atau sekering saudara bersama-sama.
jika penghapusan terjadi dari anak kanan mengambil nilai maks anak kiri jika tidak ada underflow di anak kiri
dalam situasi sebaliknya mengambil elemen min dari kanan
Penghapusan dari simpul internal
Setiap elemen dalam sebuah node internal bertindak sebagai pemisahan nilai untuk dua sub pohon, dan ketika elemen seperti itu dihapus, dua kasus muncul. Dalam kasus pertama, kedua dari dua node anak ke kiri dan kanan dari elemen dihapus memiliki jumlah minimum elemen, yaitu L-1. Mereka kemudian dapat bergabung ke node tunggal dengan 2L-2 unsur, nomor yang tidak melebihi U-1 dan sebagainya adalah simpul hukum. Kecuali diketahui bahwa B-pohon tertentu tidak berisi data duplikat, maka kita harus juga (secara rekursif) menghapus elemen tersebut dari node yang baru.
Dalam kasus kedua, salah satu dari dua node anak mengandung lebih dari jumlah minimum elemen. Kemudian pemisah baru bagi mereka subtrees harus ditemukan. Perhatikan bahwa elemen terbesar di subtree kiri masih kurang dari separator. Demikian juga, elemen terkecil di subtree kanan adalah unsur terkecil yang masih lebih besar dari pemisah. Kedua unsur-unsur dalam node daun, dan dapat menjadi pemisah baru untuk dua sub-pohon.
Jika nilai dalam node internal, memilih pemisah baru (baik elemen terbesar di subtree kiri atau elemen terkecil di subtree kanan), keluarkan dari simpul daun itu, dan mengganti elemen yang akan dihapus dengan pemisah baru.
Ini telah dihapus elemen dari simpul daun, dan sebagainya sekarang setara dengan kasus sebelumnya.
Rebalancing setelah penghapusan
Jika menghapus sebuah elemen dari simpul daun telah membawa di bawah ukuran minimum, beberapa elemen harus didistribusikan untuk membawa semua node sampai minimum. Dalam beberapa kasus penataan ulang akan bergerak kekurangan untuk orangtua, dan redistribusi harus diterapkan iteratif atas pohon, bahkan mungkin ke akar. Karena jumlah elemen minimum tidak berlaku untuk root, membuat akar menjadi node hanya kekurangan tidak menjadi masalah. Algoritma untuk menyeimbangkan pohon adalah sebagai berikut:
Jika saudara benar memiliki lebih dari jumlah minimum elemen
Tambahkan pemisah ke ujung node kekurangan.
Ganti pemisah di orangtua dengan elemen pertama dari saudara yang benar.
Menambahkan anak pertama dari saudara tepat sebagai anak terakhir dari node kekurangan
Jika tidak, jika saudara kiri memiliki lebih dari jumlah minimum elemen.
Tambahkan pemisah ke awal dari node kekurangan.
Ganti pemisah di orangtua dengan elemen terakhir dari saudara kiri.
Masukkan anak terakhir dari saudara kiri sebagai anak pertama dari node kekurangan
Jika kedua saudara langsung hanya memiliki jumlah minimum elemen
Buat node baru dengan semua elemen dari node kekurangan, semua elemen dari salah satu saudara, dan pemisah di induk antara dua node saudara gabungan.
Hapus pemisah dari orangtua, dan mengganti dua anak-anak itu dipisahkan dengan node gabungan.
Jika yang membawa jumlah elemen dalam induk di bawah minimum, ulangi langkah-langkah dengan node kekurangan, kecuali root, karena root yang diizinkan untuk menjadi kekurangan.
Kasus-satunya untuk menjelaskan adalah ketika akar tidak memiliki elemen dan satu anak. Dalam hal ini cukup untuk menggantinya dengan anak satu-satunya.
B-Tree di filesystem
Selain penggunaannya dalam database, B-Tree juga digunakan dalam filesystem untuk memungkinkan akses acak cepat ke sebuah blok yang sewenang-wenang dalam sebuah file tertentu. Masalah dasar adalah memutar file blok saya alamat ke blok disk (atau mungkin untuk sektor silinder-kepala-) alamat.
Beberapa sistem operasi membutuhkan pengguna untuk mengalokasikan ukuran maksimum file ketika file tersebut dibuat. File kemudian dapat dialokasikan sebagai blok disk berdekatan. Mengubah ke blok disk: sistem operasi hanya menambahkan alamat blok file ke awal blok disk dari file. Skema sederhana, tetapi file tersebut tidak dapat melebihi ukurannya dibuat.
Sistem operasi lainnya memperbolehkan file untuk tumbuh. Blok disk yang dihasilkan mungkin tidak berdekatan, sehingga pemetaan blok logis untuk blok fisik lebih terlibat.
MS-DOS, misalnya, menggunakan Tabel Alokasi File sederhana (FAT). FAT memiliki sebuah entri untuk setiap blok disk, [catatan 1] dan entri yang mengidentifikasi apakah blok yang digunakan oleh file dan jika demikian, yang blok (jika ada) adalah blok disk berikutnya dari file yang sama. Jadi, alokasi setiap file direpresentasikan sebagai linked list dalam tabel. Dalam rangka untuk mencari alamat disk blok i file, sistem operasi (atau utilitas disk) berurutan harus mengikuti daftar file terkait dalam FAT. Lebih buruk lagi, untuk menemukan blok disk gratis, berurutan harus scan FAT. Untuk MS-DOS, itu bukan hukuman besar karena disk dan file yang kecil dan FAT memiliki beberapa entri dan rantai file yang relatif singkat. Dalam filesystem FAT12 (digunakan pada floppy disk dan hard disk awal), tidak ada lebih dari 4.080 [catatan 2] entri, dan FAT biasanya akan menetap di memori. Sebagai disk menjadi lebih besar, arsitektur FAT mulai menghadapi hukuman. Pada disk besar menggunakan FAT, mungkin perlu untuk melakukan disk membaca untuk mempelajari lokasi disk dari blok file yang akan dibaca atau ditulis.
TOPS-20 (dan mungkin TENEX) digunakan pohon 0 sampai 2 tingkat yang memiliki kesamaan dengan Pohon-B [rujukan?]. Sebuah blok disk adalah 512 36-bit kata-kata. Jika file disimpan dalam sebuah blok kata 512 (29), maka direktori file akan menunjuk ke blok disk fisik. Jika cocok file dalam 218 kata, maka direktori akan menunjuk ke indeks aux, yang 512 kata-kata indeks yang baik akan menjadi NULL (blok tidak dialokasikan) atau titik ke alamat fisik blok. Jika cocok file dalam 227 kata, maka direktori akan menunjuk ke blok memegang aux-aux indeks; setiap entri baik akan menjadi NULL atau titik ke indeks aux. Akibatnya, blok disk fisik untuk file kata 227 bisa ditemukan di dua disk membaca dan membaca ketiga.
Apple filesystem HFS +, Microsoft NTFS [4] dan beberapa filesystem Linux, seperti Btrfs dan ext4, menggunakan B-pohon.
Lehman dan Yao menunjukkan bahwa semua kunci membaca bisa dihindari (dan dengan demikian sangat meningkatkan akses bersamaan) dengan menghubungkan blok pohon di setiap tingkat bersama-sama dengan pointer "berikutnya". Hal ini menghasilkan struktur pohon di mana kedua operasi penyisipan dan pencarian turun dari akar ke daun. Kunci menulis hanya diperlukan sebagai blok pohon dimodifikasi. Hal ini memaksimalkan konkurensi akses oleh beberapa pengguna, suatu pertimbangan penting untuk database dan / atau B-Tree berbasis ISAM metode penyimpanan. Biaya yang terkait dengan peningkatan ini adalah bahwa halaman kosong tidak dapat dihapus dari btree selama operasi normal. Namun, untuk berbagai strategi untuk mengimplementasikan penggabungan node.
Paten Amerika Serikat 5283894, diberikan Pada tahun 1994, muncul untuk menunjukkan cara untuk menggunakan 'Meta Metode Akses' untuk memungkinkan bersamaan B + Tree akses dan modifikasi tanpa kunci. Teknik mengakses 'ke atas' pohon untuk kedua pencarian dan update dengan cara tambahan dalam-memori indeks titik di blok di setiap tingkat dalam cache blok. Tidak ada reorganisasi untuk menghapus diperlukan dan tidak ada 'berikutnya' pointer di blok masing-masing di Lehman dan Yao.
Selain penggunaannya dalam database, B-Tree juga digunakan dalam filesystem untuk memungkinkan akses acak cepat ke sebuah blok yang sewenang-wenang dalam sebuah file tertentu. Masalah dasar adalah memutar file blok saya alamat ke blok disk (atau mungkin untuk sektor silinder-kepala-) alamat.
Beberapa sistem operasi membutuhkan pengguna untuk mengalokasikan ukuran maksimum file ketika file tersebut dibuat. File kemudian dapat dialokasikan sebagai blok disk berdekatan. Mengubah ke blok disk: sistem operasi hanya menambahkan alamat blok file ke awal blok disk dari file. Skema sederhana, tetapi file tersebut tidak dapat melebihi ukurannya dibuat.
Sistem operasi lainnya memperbolehkan file untuk tumbuh. Blok disk yang dihasilkan mungkin tidak berdekatan, sehingga pemetaan blok logis untuk blok fisik lebih terlibat.
MS-DOS, misalnya, menggunakan Tabel Alokasi File sederhana (FAT). FAT memiliki sebuah entri untuk setiap blok disk, [catatan 1] dan entri yang mengidentifikasi apakah blok yang digunakan oleh file dan jika demikian, yang blok (jika ada) adalah blok disk berikutnya dari file yang sama. Jadi, alokasi setiap file direpresentasikan sebagai linked list dalam tabel. Dalam rangka untuk mencari alamat disk blok i file, sistem operasi (atau utilitas disk) berurutan harus mengikuti daftar file terkait dalam FAT. Lebih buruk lagi, untuk menemukan blok disk gratis, berurutan harus scan FAT. Untuk MS-DOS, itu bukan hukuman besar karena disk dan file yang kecil dan FAT memiliki beberapa entri dan rantai file yang relatif singkat. Dalam filesystem FAT12 (digunakan pada floppy disk dan hard disk awal), tidak ada lebih dari 4.080 [catatan 2] entri, dan FAT biasanya akan menetap di memori. Sebagai disk menjadi lebih besar, arsitektur FAT mulai menghadapi hukuman. Pada disk besar menggunakan FAT, mungkin perlu untuk melakukan disk membaca untuk mempelajari lokasi disk dari blok file yang akan dibaca atau ditulis.
TOPS-20 (dan mungkin TENEX) digunakan pohon 0 sampai 2 tingkat yang memiliki kesamaan dengan Pohon-B [rujukan?]. Sebuah blok disk adalah 512 36-bit kata-kata. Jika file disimpan dalam sebuah blok kata 512 (29), maka direktori file akan menunjuk ke blok disk fisik. Jika cocok file dalam 218 kata, maka direktori akan menunjuk ke indeks aux, yang 512 kata-kata indeks yang baik akan menjadi NULL (blok tidak dialokasikan) atau titik ke alamat fisik blok. Jika cocok file dalam 227 kata, maka direktori akan menunjuk ke blok memegang aux-aux indeks; setiap entri baik akan menjadi NULL atau titik ke indeks aux. Akibatnya, blok disk fisik untuk file kata 227 bisa ditemukan di dua disk membaca dan membaca ketiga.
Apple filesystem HFS +, Microsoft NTFS [4] dan beberapa filesystem Linux, seperti Btrfs dan ext4, menggunakan B-pohon.
Lehman dan Yao menunjukkan bahwa semua kunci membaca bisa dihindari (dan dengan demikian sangat meningkatkan akses bersamaan) dengan menghubungkan blok pohon di setiap tingkat bersama-sama dengan pointer "berikutnya". Hal ini menghasilkan struktur pohon di mana kedua operasi penyisipan dan pencarian turun dari akar ke daun. Kunci menulis hanya diperlukan sebagai blok pohon dimodifikasi. Hal ini memaksimalkan konkurensi akses oleh beberapa pengguna, suatu pertimbangan penting untuk database dan / atau B-Tree berbasis ISAM metode penyimpanan. Biaya yang terkait dengan peningkatan ini adalah bahwa halaman kosong tidak dapat dihapus dari btree selama operasi normal. Namun, untuk berbagai strategi untuk mengimplementasikan penggabungan node.
Paten Amerika Serikat 5283894, diberikan Pada tahun 1994, muncul untuk menunjukkan cara untuk menggunakan 'Meta Metode Akses' untuk memungkinkan bersamaan B + Tree akses dan modifikasi tanpa kunci. Teknik mengakses 'ke atas' pohon untuk kedua pencarian dan update dengan cara tambahan dalam-memori indeks titik di blok di setiap tingkat dalam cache blok. Tidak ada reorganisasi untuk menghapus diperlukan dan tidak ada 'berikutnya' pointer di blok masing-masing di Lehman dan Yao.
berikut link yang menampilkan animasi B-Tree : http://slady.net/java/bt/view.php
