Apa perbedaan antara pohon B dan pohon B +?

293

Dalam b-tree Anda bisa menyimpan kunci dan data di internal dan node leaf , tetapi di b + tree Anda harus menyimpan data di node leaf saja .

Apakah ada keuntungan melakukan hal di atas dalam pohon b +?

Mengapa tidak menggunakan b-tree daripada b + tree di mana-mana, karena secara naluri mereka tampak lebih cepat?

Maksud saya, mengapa Anda perlu mereplikasi kunci (data) dalam pohon b +?

database data-structures simplfuzz
sumber
37
Saya pikir apa yang mereka katakan adalah "B-Tree" vs. B + -Tree. Mereka berarti tanda hubung, bukan tanda minus.
stu

Jawaban:

421

Gambar di bawah ini membantu menunjukkan perbedaan antara pohon B + dan pohon B.

Keuntungan dari pohon B +:

  • Karena pohon B + tidak memiliki data yang terkait dengan node interior, lebih banyak tombol dapat muat pada halaman memori. Oleh karena itu, diperlukan lebih sedikit cache yang hilang untuk mengakses data yang ada di leaf node.
  • Node daun dari pohon B + dihubungkan, sehingga melakukan pemindaian penuh semua objek dalam pohon hanya membutuhkan satu linear melewati semua node daun. Pohon AB, di sisi lain, akan memerlukan traversal dari setiap tingkat di pohon. Traversal full-tree ini kemungkinan akan melibatkan lebih banyak cache misses daripada traversal linear dari daun B +.

Keuntungan dari pohon B:

  • Karena pohon B berisi data dengan masing-masing kunci, node yang sering diakses dapat berada lebih dekat ke root, dan karenanya dapat diakses lebih cepat.

Pohon B dan B +

Rose Perrone
sumber
2
Apakah ada kendala pada jumlah entri dalam simpul daun ??
TLE
38
@TLE Pertanyaan bagus! Iya. Hard drive mengakses minimal satu halaman memori pada satu waktu, jadi kami ingin mencocokkan semua pointer dalam satu halaman memori. Kami ingin hanya membutuhkan satu disk baca per akses daun, jadi kami tidak ingin menetapkan lebih dari satu ukuran halaman petunjuk untuk daun. Jika kita mengisi daun dengan ukuran halaman pointer, dan kemudian kita ingin menambahkan pointer lain ke daun ini, kita membuat dua anak dari simpul ini, dan memberikan setengah dari pointer daun untuk setiap anak baru. Tentu saja, mungkin ada beberapa perombakan untuk memastikan ketinggian pohon dijaga agar tetap minimum. Apakah ini membantu?
Rose Perrone
pointer terakhir dari setiap simpul daun B-tree harus menunjuk ke simpul daun berikutnya, kan?
camino
8
Maaf karena menabrak utas lama seperti itu, tetapi komentar @ Babyburger tentang bagaimana komentar camino itu benar sebenarnya tidak benar; B-Tree tidak terhubung ke node daun. A B +, tentu saja.
Jason
Terima kasih atas jawaban yang sangat baik, apa gunanya kasus ketika pemindaian penuh objek akan diperlukan dalam pohon B / B + dalam konteks database? Karena ini terutama digunakan untuk pengindeksan, pencarian hampir tidak pernah perlu memindai seluruh pohon dengan benar dan sebaliknya melintasi melalui jalur indeks, apakah itu benar?
Siddhartha
113

Keuntungan utama dari pohon B + di atas pohon B adalah mereka memungkinkan Anda untuk mengemas lebih banyak pointer ke node lain dengan menghapus pointer ke data, sehingga meningkatkan fanout dan berpotensi mengurangi kedalaman pohon.

Kerugiannya adalah tidak ada out awal ketika Anda mungkin menemukan kecocokan di simpul internal. Tetapi karena kedua struktur data memiliki fanout yang besar, sebagian besar pertandingan Anda akan berada pada node daun, membuat rata-rata pohon B + lebih efisien.

Vic E
sumber
1
Saya lebih suka jawaban Jeff, karena menekankan perbedaan efisiensi ketika melakukan pemindaian penuh.
Rose Perrone
Saya benar-benar bingung karena melintasi b-tree menggunakan in-order traversal akan membaca semua nilai dalam urutan diurutkan dalam waktu O (n). Jika setiap simpul pohon ukuran optimal untuk ukuran halaman fisik, sepertinya hal-hal tidak mendapatkan yang lebih optimal. Sebaliknya, biaya untuk mendapatkan nilai pertama (terkecil) dalam pohon b + adalah O (log n) dan kemudian berjalan melalui setiap daun adalah O (n) sehingga total biaya adalah O (log n + n). Ini lebih banyak pekerjaan dan lebih banyak membaca disk yang masuk akal karena pohon memiliki semua data tambahan ini di dalamnya. Saya tidak mengerti.
Eric
Apa kata lain untuk 'fanout' dalam kalimat di atas?
Jorge Bucaran
3
@JorgeBucaran fanout = jumlah tepi yang keluar dari sebuah simpul
bantmen
33

B + Trees jauh lebih mudah dan berkinerja lebih tinggi untuk melakukan pemindaian penuh, seperti dalam melihat setiap bagian data yang diindeks pohon, karena simpul terminal membentuk daftar tertaut. Untuk melakukan pemindaian penuh dengan B-Tree Anda perlu melakukan traversal pohon lengkap untuk menemukan semua data.

B-Pohon di sisi lain bisa lebih cepat ketika Anda melakukan pencarian (mencari sepotong data tertentu dengan kunci) terutama ketika pohon berada di RAM atau penyimpanan non-blok lainnya. Karena Anda dapat meningkatkan node yang biasa digunakan di pohon, ada sedikit perbandingan yang diperlukan untuk mendapatkan data.

Jeff Mc
sumber
1
Apakah Anda setuju maka pohon B + akan digunakan untuk situasi di mana mungkin ada membaca berurutan di semua data sehingga dapat pergi melintasi daun. Sedangkan pohon B akan ideal untuk situasi Akses Acak?
JDPeckham
31
  1. Dalam pohon B kunci pencarian dan data disimpan dalam node internal atau daun. Tetapi dalam B + -tree data disimpan hanya dalam node daun.
  2. Pemindaian penuh pohon B + sangat mudah karena semua data ditemukan dalam simpul daun. Pemindaian penuh pohon B membutuhkan traversal penuh.
  3. Dalam pohon B, data dapat ditemukan dalam node daun atau node internal. Penghapusan node internal sangat rumit. Dalam pohon B +, data hanya ditemukan di simpul daun. Menghapus simpul daun itu mudah.
  4. Penyisipan dalam pohon B lebih rumit daripada pohon B +.
  5. Pohon B + menyimpan kunci pencarian yang berlebihan, tetapi pohon B tidak memiliki nilai yang berlebihan.
  6. Dalam pohon B +, data simpul daun disusun sebagai daftar tertaut berurutan tetapi dalam pohon B simpul daun tidak dapat disimpan menggunakan daftar tertaut. Banyak implementasi sistem basis data lebih menyukai kesederhanaan struktur pohon B +.
androidcodehunter
sumber
15

Contoh dari konsep sistem Database ke-5

B + -tree Pohon B +

pohon-B yang sesuai Btree

camino
sumber
5
Saya tidak berpikir B-Tree memiliki tautan ke anak-anak simpul. Misalnya dari Clearview bucketke Mianus Bucket. Lagipula tidak masuk akal untuk melakukan itu karena di antara keduanya Anda memiliki Downtown bucketyang banyak dicari jika Anda ingin melakukan Pemindaian Indeks dalam B-tree (membutuhkan pengulangan jejak). Dimana kamu mendapatkan ini?
Evan Carroll
1
@EvanCarroll Konsep sistem basis data ke-5, mungkin Anda perlu mengonfirmasi dengan penulis :)
camino
11

Tentukan "lebih cepat". Secara asimtotik mereka hampir sama. Perbedaannya terletak pada bagaimana mereka menggunakan penyimpanan sekunder. Artikel Wikipedia tentang pohon - B dan pohon B + terlihat cukup dapat dipercaya.

Charlie Martin
sumber
2
Saya setuju dengan Charlie. Karena satu node dari B-Tree mewakili satu halaman memori sekunder atau blok, bagian dari satu node ke yang lain membutuhkan perubahan halaman yang memakan waktu.
11

Adegoke A, Amit

Saya kira satu hal penting yang Anda lewatkan adalah perbedaan antara data dan petunjuk sebagaimana dijelaskan di bagian ini.

Pointer: pointer ke node lain.

Data: - Dalam konteks indeks basis data, data hanyalah penunjuk ke data nyata (baris) yang berada di tempat lain.

Oleh karena itu dalam kasus B tree setiap node memiliki tiga kunci informasi, pointer ke data yang terkait dengan kunci dan pointer ke node anak.

Dalam B + tree internal node menyimpan kunci dan pointer ke simpul anak, sedangkan leaf node menyimpan kunci dan pointer ke data terkait. Ini memungkinkan lebih banyak jumlah kunci untuk ukuran node tertentu. Ukuran node ditentukan terutama oleh ukuran blok.

Keuntungan memiliki lebih banyak kunci per node dijelaskan di atas sehingga saya akan menghemat usaha pengetikan saya.

Saket
sumber
10

B + Trees sangat bagus dalam penyimpanan berbasis blok (mis: hard disk). dengan mengingat hal ini, Anda mendapatkan beberapa keuntungan, misalnya (dari atas kepala saya):

  • fanout tinggi / kedalaman rendah: itu berarti Anda harus mendapatkan lebih sedikit blok untuk mendapatkan data. dengan data yang bercampur dengan pointer, setiap pembacaan mendapat pointer yang lebih sedikit, jadi Anda perlu lebih banyak upaya untuk sampai ke data

  • penyimpanan blok sederhana dan konsisten: simpul dalam memiliki N pointer, tidak ada yang lain, simpul daun memiliki data, tidak ada yang lain. yang membuatnya mudah untuk mengurai, men-debug dan bahkan merekonstruksi.

  • Kepadatan kunci yang tinggi berarti node teratas hampir pasti pada cache, dalam banyak kasus semua node batin cepat di-cache, sehingga hanya akses data yang harus pergi ke disk.

Javier
sumber
2
sebagian besar untuk pohon dalam memori; tetapi ada opsi populer lainnya, seperti pohon merah-hitam, lewati daftar, dan semacamnya.
Javier
B-tree juga dirancang untuk penyimpanan berbasis blok yang efisien, membatasi jumlah akses node asimptotik. Jika tidak, jika menggunakan media penyimpanan seperti memori dengan akses acak, seseorang dapat menggunakan pohon biner yang dapat menyeimbangkan diri sendiri seperti pohon merah-hitam untuk mencapai hasil yang lebih baik.
dionyziz
tidak seharusnya poin pertama Anda mengatakan "kurang mencari" daripada "mencari lebih banyak". Kedalaman yang lebih kecil -> less seek
Jesse
1
@Jesse: fanout tinggi => kedalaman rendah => lebih sedikit mencari, tetapi mencampur data dan pointer berarti lebih sedikit pointer => kipas rendah => lebih mendalam => lebih banyak pencarian
Javier
1
@ AdegokeA: pohon B + memiliki dua jenis node: node batin dengan hanya kunci dan pointer, tidak ada data; dan leaf node, dengan data dan tanpa pointer. yang memungkinkan jumlah kunci maksimum pada setiap simpul dalam. jika Anda menyimpan data pada simpul dalam, maka Anda bisa memasukkan lebih sedikit pointer dan pohon Anda menjadi lebih tinggi.
Javier
5

Dalam B + Tree, karena hanya pointer yang disimpan di node internal, ukurannya menjadi jauh lebih kecil daripada node internal B tree (yang menyimpan kedua data + kunci). Oleh karena itu, indeks pohon B + dapat diambil dari penyimpanan eksternal dalam satu disk baca, diproses untuk menemukan lokasi target. Jika sudah menjadi pohon B, pembacaan disk diperlukan untuk setiap proses pengambilan keputusan. Saya harap saya menjelaskan maksud saya! :)

VS7
sumber
4

**

Kelemahan utama B-Tree adalah sulitnya melintasi tombol secara berurutan. B + Tree mempertahankan properti akses acak cepat dari B-Tree dan juga memungkinkan akses sekuensial cepat

** ref: Struktur Data Menggunakan C // Penulis: Aaro M Tenenbaum

http://books.google.co.in/books?id=X0Cd1Pr2W0gC&pg=PA456&lpg=PA456&dq=drawback+of+B-Tree+is+the+difficulty+of+Traversing+the+keys+ollowently&source=bl&ots=pGsQSE F9MY7zEXYAMVKl_Sg4W-0LTRor8 & hl = en & sa = X & ei = nD5AUbeeH4zwrQe12oCYAQ & ved = 0CDsQ6AEwAg # v = onepage & q = kekurangan% 20 dari% 20B-% pohon% 20% karena%%% karena% 20% karena%% sulit karena% 20% karena% 20% karena%% sulit karena% 20% karena% 20% naik% karena% 20% sulit karena% 20% naik% karena% 20% naik.

Kapil Kumar
sumber
1
Ini seharusnya jawaban yang benar. Singkatnya: Lokalitas referensi.
Theodore Zographos
2

Ambil satu contoh - Anda memiliki tabel dengan data besar per baris. Itu berarti setiap instance objek adalah Big.

Jika Anda menggunakan pohon B di sini maka sebagian besar waktu dihabiskan memindai halaman dengan data - yang tidak berguna. Dalam database itulah alasan menggunakan B + Trees untuk menghindari pemindaian data objek.

B + Pohon memisahkan kunci dari data.

Tetapi jika ukuran data Anda kurang dari maka Anda dapat menyimpannya dengan kunci yang merupakan apa yang dilakukan B tree.

Amit
sumber
1
"Jika Anda menggunakan pohon B di sini maka sebagian besar waktu dihabiskan memindai halaman dengan data" - tidak perlu. Simpul B-tree hanya dapat menyimpan "pointer" ke data pada disk, bukan data itu sendiri.
TT_
2

Perbedaan utama antara B-tree dan B + tree adalah bahwa B-tree menghilangkan penyimpanan berlebihan dari nilai-nilai kunci pencarian. Karena kunci pencarian tidak diulang dalam B-tree, kita mungkin tidak dapat menyimpan indeks menggunakan lebih sedikit node pohon daripada dalam indeks pohon B + yang sesuai. Namun, karena kunci pencarian yang muncul di node non-daun tidak muncul di tempat lain di B-tree, kami dipaksa untuk menyertakan bidang penunjuk tambahan untuk setiap kunci pencarian di simpul non-daun. Ini adalah keuntungan ruang untuk B-tree, karena pengulangan tidak terjadi dan dapat digunakan untuk indeks besar.

Mary
sumber
1
Menarik, pemikiran tentang pengulangan adalah unik di antara balasan di sini dan lebih masuk akal daripada traversal b-tree yang lebih berurutan menjadi lebih efisien daripada traversal b-tree yang berurutan. Sejauh yang saya tahu, itu tidak sepenuhnya benar, atau tidak seluruh cerita seperti dalam urutan traversal dari b-tree adalah O (n) dan menemukan simpul terkecil dalam pohon b + adalah O (log n) dan kemudian melintasi setiap daun adalah O (n) di samping itu. Namun, jika Anda mengindeks sesuatu dengan rentang nilai yang kecil, seperti bidang boolean, pohon b + jauh lebih masuk akal daripada pohon-b karena penanganan duplikatnya.
Eric
1

Pohon B + adalah pohon seimbang di mana setiap jalur dari akar pohon ke daun memiliki panjang yang sama, dan setiap simpul pohon tanpa daun memiliki antara [n / 2] dan [n] anak-anak, di mana n adalah diperbaiki untuk pohon tertentu. Ini berisi halaman indeks dan halaman data. Pohon biner hanya memiliki dua anak per simpul orangtua, pohon B + dapat memiliki jumlah variabel anak untuk setiap simpul induk

Vivek Rakholiya
sumber
1
Hanya untuk kejelasan, pohon B bukan pohon biner. Bahkan, pohon B dan pohon B + lebih dekat satu sama lain dalam konstruksi dan penggunaan daripada pohon biner. Artikel wiki dapat membantu dalam menghapus definisi - B + Tree , B Tree dan Binary Tree
uutsav
1

Salah satu kemungkinan penggunaan pohon B + adalah bahwa pohon ini cocok untuk situasi di mana pohon tumbuh sangat besar sehingga tidak sesuai dengan memori yang tersedia. Dengan demikian, Anda biasanya mengharapkan untuk melakukan beberapa I / O.
Itu sering terjadi bahwa pohon B + digunakan bahkan ketika itu sebenarnya cocok dengan memori, dan kemudian manajer cache Anda mungkin menyimpannya di sana secara permanen. Tapi ini adalah kasus khusus, bukan yang umum, dan kebijakan caching terpisah dari pemeliharaan pohon B +.

Juga, dalam pohon B +, halaman daun dihubungkan bersama dalam daftar yang ditautkan (atau daftar yang ditautkan dua kali lipat), yang mengoptimalkan traversal (untuk pencarian rentang, pengurutan, dll.). Jadi jumlah pointer adalah fungsi dari algoritma spesifik yang digunakan.

stack programmer
sumber
Hal ini untuk menjawab pertanyaan yang mengapa kita tidak menggunakan B-pohon bukan B + pohon di mana-mana :)
tumpukan programmer
3
Tetapi Anda hanya menggambarkan satu sisi, sejauh yang kami tahu, dengan jawaban Anda b-pohon bisa berfungsi dengan cara yang persis sama. OP diminta untuk menjelaskan perbedaannya dan Anda hanya membicarakan satu dan bukan yang lain. Anda tidak dapat memiliki diagram venn dengan satu lingkaran!
Malfist