Почему не B+-дерево MongoDB

Кто-нибудь знает, почему MongoDB использует B-Tree, а не B+-Tree?

Насколько я знаю, большинство СУБД используют B+-Tree. Есть ли какая-то особая причина для MongoDB использовать B-Tree?

Благодарю.


mongodb geospatial spatial-index b-tree
person dykw    schedule 02.04.2013    source источник
comment
Хотя это интересный вопрос, я не думаю, что кто-то сможет дать окончательный ответ, не спросив самих сотрудников MongoDB.   -  person templatetypedef    schedule 02.04.2013
comment
Я отправил электронное письмо на 10gen. Они попросили меня опубликовать свой вопрос на их форуме MongoDB. Но не думаю, что многие читают форум. У меня нет ответа.   -  person dykw    schedule 02.04.2013
comment
Вы спросили это 4 часа назад (с момента моего комментария). Будьте немного терпеливее. Кроме того, они могут не захотеть тратить время на ответ на ваш вопрос.   -  person WiredPrairie    schedule 02.04.2013
comment
Согласно этому документу, WiredTiger поддерживает данные таблицы в памяти, используя структуру данных, называемую B-дерево (дерево B+, если быть точным)   -  person zangw    schedule 07.05.2020

Ответы (3)


arrow_upward
2
arrow_downward

Вопрос смутил меня, когда я выучил B/B+. Теперь я получил несколько ответов:

  1. mysql является относительным db, а mongo - нет. Это означает, что мы делаем больше операций с диапазонами в mysql (например, select * from xx where id > 23). Так что преимущества дерева B+ неочевидны.
  2. Лучшее время поиска дерева B равно O(1), тогда как B+ всегда равно O(log n). Поэтому при поиске некоторых «горячих» данных. B-дерево имеет лучшую производительность (однако, если вы всегда ищете данные в листе при использовании B-дерева, это занимает больше времени дискового ввода-вывода, поэтому оно может работать плохо).

На мой взгляд, это зависит от деталей реализации mongo. Но я не разработчик Mongo. :D

person 陈Jifan    schedule 22.07.2019
comment
Вы также можете выполнять запросы диапазона в MongoDB. - person Thilo; 22.07.2019

arrow_upward
1
arrow_downward

MongoDB использует механизм хранения B+ от WiredTiger по умолчанию.

1、https://docs.mongodb.com/manual/core/wiredtiger/

Начиная с MongoDB 3.2 механизм хранения WiredTiger является механизмом хранения по умолчанию.

2、http://source.wiredtiger.com/3.2.1/tune_page_size_and_comp.html

WiredTiger поддерживает данные таблицы в памяти, используя структуру данных, называемую B-Tree (B+ Tree, если быть точным), обращаясь к узлам B-Tree как к страницам. Внутренние страницы содержат только ключи. Конечные страницы хранят как ключи, так и значения.

person Font Ding    schedule 15.01.2021

arrow_upward
0
arrow_downward

Насколько я понимаю, MongoDB хранит индексы как часть тех же файлов, в которых хранятся данные. Так что B Tree лучше! Дерево B+ хранит данные только в листьях.

person Community    schedule 24.04.2015