Я делаю проект, в котором мне требуется структура данных btree или b+tree. Кто-нибудь знает о существующей реализации btree или b+tree (с алгоритмами вставки, удаления, поиска)? Он должен принимать строку в качестве входных данных и формировать btree или b+tree из этих строк.
Существующая реализация Btree или B+tree в Java [закрыта]
comment
@rohit: я немного отредактировал ваш вопрос, чтобы сделать его менее очевидным кандидатом на вопрос, близкий как ненастоящий. Если вам не нравятся мои изменения, вы можете отменить их.
- person Jørn Schou-Rode schedule 04.04.2010
comment
Можете ли вы уточнить, для чего вы собираетесь использовать структуру данных?
- person Graphics Noob schedule 04.04.2010
Ответы (4)
За неимением подробностей о проблеме, которую вам нужно решить, я позволю себе предложить альтернативное решение, которое может решить вашу проблему: вместо этого используйте красное/черное дерево.
Красно-черное дерево можно рассматривать как b-дерево, как описано в Википедии. :
Красно-черное дерево похоже по структуре на B-дерево порядка 4, где каждый узел может содержать от 1 до 3 значений и (соответственно) от 2 до 4 дочерних указателей. В таком B-дереве каждый узел будет содержать только одно значение, соответствующее значению в черном узле красно-черного дерева, с необязательным значением до и/или после него в том же узле, оба соответствуют эквивалентному красному узлу дерева. красно-черное дерево [...]
В Java есть два встроенных класса: TreeMap. и TreeSet, предоставляющий красные/черные деревья. Ни один из них не будет принимать строку в качестве входных данных и выращивать из нее дерево, но вы можете реализовать что-то подобное «вокруг» одного из этих классов.
person
Jørn Schou-Rode
schedule
04.04.2010
jdbm имеет очень надежную реализацию b+tree. Также h+tree — интересная связанная структура данных.
person
Kevin Day
schedule
05.04.2010
С тех пор появились JDBM3 и JDBM4, который был переименован в MapDB.
- person Peter Lamberg; 29.12.2013
@PeterLamberg да, MapDB обещает стать очень хорошим проектом. Еще несколько недель до первого стабильного релиза, но выглядит очень хорошо. Обратите внимание, что MapDB не использует b+tree b/c требований параллелизма — я полагаю, что они используют какое-то связанное дерево.
- person Kevin Day; 02.01.2014
Вот моя дисковая реализация B+-дерева. github.com/myui/btree4j
- person myui; 27.03.2019
Мне пришлось реализовать свои собственные код.
person
Justin
schedule
13.05.2012
Не проверял, но метод разделения был тем, что я искал с каждой вставкой и удалением. Только с двумя элементами это будет происходить почти все время. Вопрос: Вы перемешиваете элемент верхнего уровня? Скажем, у вас есть данные от 1 до 5000 (5000 ради этого комментария), и у вас есть первый элемент как 300, не имеет ли смысл иметь его как можно ближе к 2500?
- person Mukus; 18.02.2013
кстати .. +1 за ваш ответ.
- person Mukus; 18.02.2013
@TejaswiRana Я тестировал 5000 элементов (1-5000), и корень получил значение 2048. Реализация по умолчанию - 2-3 дерева, но это было только для целей тестирования. Вы можете передать порядок (minKeySize) дерева в конструкторе.
- person Justin; 18.02.2013
Вы можете попробовать BTree от Electric. (страница автора здесь).
person
Charles Goodwin
schedule
18.08.2011
