Implementasi Btree atau B+tree yang ada di Java [ditutup]

Saya sedang melakukan proyek yang memerlukan struktur data btree atau b+tree. Adakah yang tahu implementasi btree atau b+tree yang ada (dengan algoritma penyisipan, penghapusan, pencarian)? Itu harus menerima string sebagai input dan membentuk btree atau b+tree dari string ini.


java data-structures b-tree
person rohit    schedule 04.04.2010    source sumber
comment
@rohit: Saya telah melakukan beberapa pengeditan pada pertanyaan Anda untuk menjadikannya kandidat yang kurang jelas karena bukan pertanyaan yang sebenarnya. Jika Anda tidak menyukai perubahan saya, silakan kembalikan.   -  person Jørn Schou-Rode    schedule 04.04.2010
comment
Bisakah Anda menguraikan untuk apa Anda akan menggunakan struktur data?   -  person Graphics Noob    schedule 04.04.2010

Jawaban (4)


arrow_upward
16
arrow_downward

Karena kurangnya rincian tentang masalah yang perlu Anda selesaikan, saya akan membiarkan diri saya menyarankan solusi alternatif yang mungkin menyelesaikan masalah Anda: gunakan pohon merah/hitam sebagai gantinya.

Pohon merah/hitam dapat dianggap sebagai pohon-b, seperti yang dijelaskan di Wikipedia:

Pohon merah-hitam memiliki struktur yang mirip dengan pohon B berorde 4, di mana setiap simpul dapat berisi antara 1 hingga 3 nilai dan (sesuai) antara 2 hingga 4 penunjuk anak. Dalam B-tree tersebut, setiap node hanya akan berisi satu nilai yang cocok dengan nilai dalam node hitam dari pohon merah-hitam, dengan nilai opsional sebelum dan/atau sesudahnya dalam node yang sama, keduanya cocok dengan node merah yang setara dari pohon merah-hitam. pohon merah-hitam [...]

Java memiliki dua kelas bawaan, TreeMap dan TreeSet, menyediakan pohon merah/hitam. Tak satu pun dari ini akan mengambil string sebagai input dan menumbuhkan pohon darinya, tetapi Anda mungkin dapat mengimplementasikan sesuatu yang serupa "di sekitar" salah satu kelas tersebut.

person Jørn Schou-Rode    schedule 04.04.2010

arrow_upward
12
arrow_downward

jdbm memiliki implementasi b+tree yang sangat solid. Juga h+tree yang merupakan struktur data terkait yang menarik.

person Kevin Day    schedule 05.04.2010
comment
Sejak itu telah ada JDBM3 dan JDBM4 yang diubah namanya menjadi MapDB. - person Peter Lamberg; 29.12.2013
comment
@PeterLamberg ya - MapDB sedang bersiap menjadi proyek yang sangat bagus. Masih beberapa minggu dari rilis stabil pertama, tapi kelihatannya sangat bagus. Perhatikan bahwa MapDB tidak menggunakan b+tree b/c persyaratan konkurensi - Saya yakin mereka menggunakan semacam pohon tertaut. - person Kevin Day; 02.01.2014
comment
Ini adalah implementasi B+-tree berbasis disk saya. github.com/myui/btree4j - person myui; 27.03.2019

arrow_upward
5
arrow_downward

Saya harus mengimplementasikan kode.

person Justin    schedule 13.05.2012
comment
Belum mengujinya tetapi metode split adalah yang saya cari pada setiap penyisipan dan penghapusan. Dengan hanya 2 elemen, hal ini akan terjadi hampir setiap saat. Pertanyaan: Apakah Anda mengacak elemen tingkat atas? Katakanlah Anda memiliki data dari 1 -5000 (5000 demi komentar ini) dan Anda memiliki elemen pertama sebagai 300, bukankah masuk akal jika mendekati 2500? - person Mukus; 18.02.2013
comment
btw.. +1 untuk jawabanmu. - person Mukus; 18.02.2013
comment
@TejaswiRana Saya telah menguji dengan 5000 elemen (1-5000) dan root berakhir dengan nilai 2048. Implementasi defaultnya adalah 2-3 pohon tetapi itu hanya untuk tujuan pengujian. Anda dapat meneruskan urutan (minKeySize) pohon di konstruktor. - person Justin; 18.02.2013

arrow_upward
1
arrow_downward

Anda dapat mencoba BTree dari Electric (halaman penulis di sini).

person Charles Goodwin    schedule 18.08.2011