Apakah derajat dan urutan hal yang sama ketika merujuk ke B-Tree

8

Saya tahu istilah perintah B-tree. Baru-baru ini saya mendengar istilah baru: B tree dengan derajat minimum 2.

Kita tahu bahwa derajat berhubungan dengan simpul tetapi berapa derajat pohon?
Apakah derajat memaksakan segala jenis pembatasan pada ketinggian pohon-B?

Deb
sumber

Jawaban:

10

Saya tidak berpikir bahwa derajat pohon adalah istilah standar dalam teori grafik atau struktur data. Derajat biasanya merupakan properti dari simpul / simpul grafik, yang menunjukkan jumlah tepi kejadiannya. Untuk pohon, terkadang Anda hanya mempertimbangkan ujung-ujungnya untuk anak-anak.

Saya kira "B-tree dengan derajat minimum 2" berarti bahwa setiap simpul memiliki setidaknya dua anak. Dengan kata lain itu adalah batas bawah untuk jumlah anak. Di sisi lain urutan pohon-B menunjukkan derajat simpul maksimal, dan karenanya merupakan batas atas.

A.Schulz
sumber
2
Ya. Inilah intinya. Degreemewakili batas bawah jumlah anak. yaitu jumlah minimum yang mungkin. Sedangkan Ordermewakili batas atas jumlah anak. yaitu. jumlah maksimum yang dimungkinkan. Terima kasih.
h8pathak
1
Derajat benar-benar istilah standar dalam teori grafik: derajat simpul adalah jumlah insiden tepi di atasnya.
David Richerby
9

Node B-Tree dapat berisi lebih dari satu nilai kunci sedangkan node BST hanya mengandung satu. Ada batas bawah dan atas pada jumlah kunci yang bisa dikandung oleh simpul. Batas ini dapat diekspresikan dalam bentuk bilangan bulat tetap yang t>=2disebut derajat minimum pohon-B.

  • Setiap node selain root harus memiliki setidaknya t-1kunci. Setiap simpul internal selain root memiliki setidaknya tanak.
  • Setiap node dapat memuat paling banyak 2t-1kunci. Oleh karena itu, simpul internal dapat memiliki paling banyak 2tanak. Kami mengatakan bahwa sebuah node penuh jika berisi persis 2t-1kunci.

Silakan klik Tautan Ini untuk memiliki dasar yang sangat baik tentang B-Tree dan Tautan Ini untuk algoritma tindak lanjut dan paling mudah ditulis dari operasi B-Tree.

Nasir
sumber
5

Saya telah melihat tiga cara untuk mengkarakterisasi B-tree sejauh ini:

  1. Dengan derajat B-tree t(baik minimum, seperti dalam buku Algoritma CLRS , atau maksimum seperti dalam B-tree Visualizer ).

    Pohon-B paling sederhana terjadi ketika t=2. Setiap simpul internal kemudian memiliki 2, 3, atau 4 anak, dan kami memiliki pohon 2-3-4 .

    Teks yang dirujuk dalam jawaban Nasir erat mengikuti definisi B-tree seperti yang diberikan dalam Algoritma dengan penjelasan rinci tentang properti tingkat minimum.

  2. Dengan L. dan U parameter, dengan batas bawah (atas) pada jumlah anak simpul dalam seharusnya memiliki (misalnya B-tree with L.=3,U=6 setara dengan B-tree dengan t=3 (keduanya memungkinkan 2-5 kunci per node),

  3. Dengan urutan B-tree m, diberikan oleh Knuth di TAOCP, Vol. 3 sedemikian rupa sehingga setiap simpul internal memiliki antaram2 dan m anak-anak.

Singkatnya:

  • Dengan karakterisasi gelar, jumlah anak yang diizinkan terikat untuk berbohong [t,2t] selang,
  • sementara L. dan U memungkinkan untuk spesifikasi yang lebih tepat dari jumlah anak (yaitu jumlah kunci per node diperbolehkan).

Berkenaan dengan bagian kedua dari pertanyaan OP ada Teorema 18.1 di Algoritma:

Jika n1, lalu untuk apa saja n-kunci B-tree T tinggi h dan tingkat minimum t2, hlHaigtn+12.

Tuan Tao
sumber
4

Urutan (m) dari B-tree mendefinisikan (maks dan min) no. anak-anak untuk simpul tertentu.

Derajat (t) dari definisi B-tree (maks dan min) no. kunci untuk simpul tertentu. Derajat didefinisikan sebagai derajat minimum pohon-B.

B-tree of order m: Semua node internal kecuali root memiliki paling banyak m anak-anak yang tidak bebas dan setidaknya ⌈m / 2⌉ anak-anak yang tidak kosong.

B-tree dengan (minimum) derajat t:

  1. setiap node memiliki paling banyak 2t-1 kunci
  2. jika simpul bukan root, ia memiliki setidaknya kunci t-1.
nrj
sumber
Selamat Datang di Ilmu Komputer ! Perhatikan bahwa Anda dapat menggunakan LaTeX di sini untuk mengeset matematika dengan cara yang lebih mudah dibaca. Lihat di sini untuk pengantar singkat.
FrankW
1

Degreemewakili batas bawah jumlah anak yang bisa dimiliki simpul di Pohon B (kecuali untuk root). yaitu jumlah minimum anak yang mungkin. Sedangkan Ordermewakili batas atas jumlah anak. yaitu. jumlah maksimum yang dimungkinkan.

B Tree properties sehubungan dengan Order

Properti B tree sehubungan dengan pesanan.

NOTE: Wikipedia juga menyatakan ini

B Tree Properties sehubungan dengan Gelar

B Tree Properties sehubungan dengan Gelar

NOTE: These can also be found in the CLRS book

hathpathak
sumber
1
Jika Anda ingin mengedit jawaban Anda, silakan gunakan tautan edit dan jangan mengirim ulang. Juga, tolong jangan menggunakan gambar sebagai konten utama dari posting Anda, karena mereka tidak dapat diakses oleh mesin pencari dan tunanetra. Jika Anda akan menggunakan gambar, Anda perlu mengutip sumbernya.
David Richerby
1
Diperbanyak, harap transkripsi gambar Anda ke dalam teks.
Evil
0

B-pohon pesanan 5 ATAU m = 5

maks anak-anak = 5

min anak-anak = ceil (m / 2) = 3


B-pohon derajat 5 ATAU t = 5

kunci maks = 2t-1

kunci min = t-1

Muhammad Rehan Qadri
sumber
3
Tolong jangan hanya menulis daftar persamaan. Jelaskan jawaban Anda sehingga sangat membantu bagi orang yang mengajukan pertanyaan.
David Richerby
1
Jawaban ini sangat membantu saya.
h8pathak
0

Terminologi B-tree tidak didefinisikan secara seragam di mana pun saya membaca , namun pertanyaan yang mendua adalah bagaimana urutan B-Tree? dan tidak banyak tentang tingkat B-Tree . Derajat berasal dari teori grafik yang menyatakannya sebagai jumlah derajat dan derajat dari simpul itu.

Dengan mana dapat disimpulkan bahwa derajat lebih erat terkait dengan jumlah pointer / anak simpul B-Tree dapat memiliki bukan nilai-nilai kunci dalam simpul.

Menurut Knuth dan Michael J. Folk , B-tree of order m adalah pohon dengan setiap simpul paling banyak memiliki anak m. Jadi sangat samar-samar kita dapat mengatakan bahwa keduanya adalah istilah yang kurang lebih setara dalam konteks B-Tree.

Ritwik
sumber