Здравствуйте, uzhas, Вы писали:

К>>А какие свойства Б-дерева нужны?

U>хранение данных(+метаданных?), алгоритмы обхода, конструирование с нуля, ручная балансировка (перестановка узлов)
U>а что же еще от дерева хотят ?

Так это тебе просто нужно дерево произвольной арности, а Б-дерево, будучи деревом поиска, как-то не очень предполагает ручную балансировку и алгоритмы обхода (казалось бы?)

Здравствуйте, Caracrist, Вы писали:

C>http://habrahabr.ru/post/169199/

C>

C>Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).

btree.h

#ifndef NDEBUG
#define NDEBUG 1
#endif

Что-то я отстал от моды — это сейчас нормальное поведение "библиотечных" хедеров?

... Что то меня дернуло поискать NDEBUG в коде ...

    if (!NDEBUG) {
      memset(&f->values, 0, max_count * sizeof(value_type));
    }

"Это не наш метод".

Я как-то убил полный месяц своего времени на создание реализации B+ дерева на плюсах. Ради интереса.

Интерес был полностью удовлетворен и я остался сидеть на AVL-дереве

http://habrahabr.ru/post/169199/

Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).

Здравствуйте, Caracrist, Вы писали:

C>

а там есть контейнер, который работает как B-tree ?

Здравствуйте, uzhas, Вы писали:

U>Здравствуйте, Caracrist, Вы писали:

C>>

U>а там есть контейнер, который работает как B-tree ?
Именно так написано в статье. Красно-черные деревья заменены на Б-деревья.

Здравствуйте, uzhas, Вы писали:

U>а там есть контейнер, который работает как B-tree ?

А какие свойства Б-дерева нужны?

Здравствуйте, Кодт, Вы писали:

К>А какие свойства Б-дерева нужны?

хранение данных(+метаданных?), алгоритмы обхода, конструирование с нуля, ручная балансировка (перестановка узлов)
а что же еще от дерева хотят ?

Здравствуйте, uzhas, Вы писали:

U>а что же еще от дерева хотят ?

вопрос уже затрагивался здесь: http://rsdn.ru/forum/cpp/5046854.flat

Автор: makdak
Дата: 28.01.13

Здравствуйте, Caracrist, Вы писали:

C>http://habrahabr.ru/post/169199/
C>

C>... cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).

Важное дополнение:

Разработчик предупреждает об отличии cpp-btree от стандартных контейнеров: поскольку любые операции вставки и удаления узлов в B-дерево аннулируют существующие итераторы, так что в случае необходимости нужно использовать безопасные версии.

Здравствуйте, Кодт, Вы писали:

К>Так это тебе просто нужно дерево произвольной арности, а Б-дерево, будучи деревом поиска, как-то не очень предполагает ручную балансировку и алгоритмы обхода (казалось бы?)

Обход Б-дерева слева направо — получение всех ключей в порядке возрастания.

dir в NTFS

Здравствуйте, Pavel Dvorkin, Вы писали:

К>>Так это тебе просто нужно дерево произвольной арности, а Б-дерево, будучи деревом поиска, как-то не очень предполагает ручную балансировку и алгоритмы обхода (казалось бы?)

PD>Обход Б-дерева слева направо — получение всех ключей в порядке возрастания.

А что, у других деревьев поиска поперечный обход иначе работает?

Алгоритмы обхода — это, хотя бы, ещё два других в глубину (восходящий и нисходящий). Для деревьев поиска они большого смысла не имеют. А вот для иерархии или для всяких куч — пригодятся.

PD>dir в NTFS

dir в NTFS хороши тем, что хранят данные вместе с ключем.
Т.е. и ключ и данные существуют в одном экземпляре

в refs отказались от такого дерева и используют "классическое", когда данные хранятся только в листах (вместе с ключами), а в узлах только ключи.
Итого в дереве какой-то ключ (например имя из 255 юникодных символов) хранится по всей высоте. в refs дисковое место не жалеют вообще.

Здравствуйте, Кодт, Вы писали:

PD>>Обход Б-дерева слева направо — получение всех ключей в порядке возрастания.
К>А что, у других деревьев поиска поперечный обход иначе работает?

Так вроде ж это одна из фишек b-деревьев (B+), что их можно эффективно последовательно обходить.

Здравствуйте, Caracrist, Вы писали:

C>http://habrahabr.ru/post/169199/

C>

C>Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).

Ха! А вектора у него нет. Но оно и понятно.

    // A boolean indicating whether the node is a leaf or not.
    bool leaf;

Ага, ага, эта переменная не нужна, просто код разрастается.

Ну и тут не всё быстро:

template <typename P>
void btree_node<P>::rebalance_right_to_left(btree_node *src, int to_move) {
  assert(parent() == src->parent());
  assert(position() + 1 == src->position());
  assert(src->count() >= count());
  assert(to_move >= 1);
  assert(to_move <= src->count());

  // Make room in the left node for the new values.
  for (int i = 0; i < to_move; ++i) {
    value_init(i + count());
  }

  // Move the delimiting value to the left node and the new delimiting value
  // from the right node.
  value_swap(count(), parent(), position());
  parent()->value_swap(position(), src, to_move - 1);

  // Move the values from the right to the left node.
  for (int i = 1; i < to_move; ++i) {
    value_swap(count() + i, src, i - 1);
  }
  // Shift the values in the right node to their correct position.
  for (int i = to_move; i < src->count(); ++i) {
    src->value_swap(i - to_move, src, i);
  }
  for (int i = 1; i <= to_move; ++i) {
    src->value_destroy(src->count() - i);
  }

  if (!leaf()) {
    // Move the child pointers from the right to the left node.
    for (int i = 0; i < to_move; ++i) {
      set_child(1 + count() + i, src->child(i));
    }
    for (int i = 0; i <= src->count() - to_move; ++i) {
      assert(i + to_move <= src->max_count());
      src->set_child(i, src->child(i + to_move));
      *src->mutable_child(i + to_move) = NULL;
    }
  }

  // Fixup the counts on the src and dest nodes.
  set_count(count() + to_move);
  src->set_count(src->count() - to_move);
}

Короче, продолжу ездить на своём велосипеде.

Здравствуйте, Кодт, Вы писали:

К>Так это тебе просто нужно дерево произвольной арности, а Б-дерево, будучи деревом поиска

елки-палки
со студенческой скамьи понимал под Б-деревьями обощение бинарных деревьев, то есть когда у родителя может быть более двух детей
вот даже статья: http://en.wikipedia.org/wiki/B%2B_tree
какой-то бардак в терминологиях

Здравствуйте, Кодт, Вы писали:

U>>а там есть контейнер, который работает как B-tree ?
К>А какие свойства Б-дерева нужны?
Лучшая эффективность по вставке/удалению, улучшенная локальность данных. Ровно как и в обычных дисковых базах данных.

Здравствуйте, uzhas, Вы писали:

К>>Так это тебе просто нужно дерево произвольной арности, а Б-дерево, будучи деревом поиска

U>елки-палки
А что не так в фомулировке выше?

U>со студенческой скамьи понимал под Б-деревьями обощение бинарных деревьев, то есть когда у родителя может быть более двух детей
U>вот даже статья: http://en.wikipedia.org/wiki/B%2B_tree
U>какой-то бардак в терминологиях

Б-дерево — это не обощение бинарных деревьев, поскольку является сбалансированном деревом поиска.

Здравствуйте, Cyberax, Вы писали:

U>>>а там есть контейнер, который работает как B-tree ?
К>>А какие свойства Б-дерева нужны?
C>Лучшая эффективность по вставке/удалению, улучшенная локальность данных. Ровно как и в обычных дисковых базах данных.

Так, собственно, гугловец это и сделал. Сохранив интерфейс set/map/multiset/multimap.
Вопрос в том, что в интерфейсе контейнера должно быть такое, что специфично именно для Б-дерева. Ну, разве что, менять размер страницы в рантайме (у него это параметр шаблона).

Здравствуйте, uzhas, Вы писали:

U>со студенческой скамьи понимал под Б-деревьями обощение бинарных деревьев, то есть когда у родителя может быть более двух детей

Видимо, препод попался неадекватный

U>вот даже статья: http://en.wikipedia.org/wiki/B%2B_tree
U>какой-то бардак в терминологиях

Даже в статье говорится, что Б+-дерево — это Б-дерево, у которого в страницах верхних ярусов только границы ключей, а сами ключи и данные — в страницах последнего яруса.

Б и Б+ — это обобщение деревьев поиска, а не двоичных деревьев вообще.

Кстати, любимое всеми красно-чёрное дерево — это эмуляция Б-дерева порядка 4 (т.н. 2-3-4-дерево) средствами бинарного. За счёт того, что каждый ключ лежит в собственном блоке памяти, операции над деревом не инвалидируют указатели, чем и воспользовались авторы STL и, затем, стандарта.

Ну и кстати, двоичное дерево (не поиска и не сбалансированное) — это фундаментальная структура данных, из которой можно сделать что угодно.
По сути, это просто набор cons-пар. Обычный линейный список — это тоже набор cons-пар, т.е. это вырожденное дерево, растущее только вправо.

Здравствуйте, Кодт, Вы писали:

К>Видимо, препод попался неадекватный

будем считать, что все же меня подводит память