Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Btree значения  [new]
sergq
Member

Откуда:
Сообщений: 661
Здравствуйте.

Возможно ответ на вопрос прост как три копейки. Пните)
Перечитал про деревья в индексах.
Везде написано, что во всех типах нод хранятся ключи . Что логично.
Но везде же вроде как написано , что значения хранятся только в листьях.
Применительно к базам данных значение это rowid. И их может быть много.

А как же те ключи , которые находятся не в листовых нодах? Как быть в данном случае со значениями ?

И такого момента применительно к хранению индексов в базах данных недопонимают .

Практически везде принято, что одна нода дерева равна одной странице. За пределы страницы нода не выходит. Количество ключей уровня дерева равно максимальному количеству , которое влезет на страницу с учётом служебной информации. Тогда слегка непонятно где ж в данной схеме хранятся значения ключей . Те самые rowid
19 май 19, 22:08    [21888406]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
sergq, судя по терминологии (rowid) это вопрос по Ораклу. Имеет смысл его перенести в профильный форум.
20 май 19, 08:49    [21888541]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
OoCc
Member

Откуда: с Кавказа
Сообщений: 1807
sergq
Здравствуйте.

Возможно ответ на вопрос прост как три копейки. Пните)
Перечитал про деревья в индексах.
Везде написано, что во всех типах нод хранятся ключи . Что логично.
Но везде же вроде как написано , что значения хранятся только в листьях.
Применительно к базам данных значение это rowid. И их может быть много.

А как же те ключи , которые находятся не в листовых нодах? Как быть в данном случае со значениями ?

И такого момента применительно к хранению индексов в базах данных недопонимают .

Практически везде принято, что одна нода дерева равна одной странице. За пределы страницы нода не выходит. Количество ключей уровня дерева равно максимальному количеству , которое влезет на страницу с учётом служебной информации. Тогда слегка непонятно где ж в данной схеме хранятся значения ключей . Те самые rowid

Я думаю тебе стоит почитать про btree.
20 май 19, 11:13    [21888663]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
alex55555
Member

Откуда:
Сообщений: 2129
sergq
А как же те ключи , которые находятся не в листовых нодах? Как быть в данном случае со значениями ?

Гугли про двоичные деревья, для начала.

В узлах производится сравнение на больше/меньше, и в результате получается направление "углубления в дерево", поэтому в узлах не ключи, а информация для принятия решения при поиске.
20 май 19, 11:14    [21888664]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
sergq
Member

Откуда:
Сообщений: 661
alex55555
sergq
А как же те ключи , которые находятся не в листовых нодах? Как быть в данном случае со значениями ?

Гугли про двоичные деревья, для начала.

В узлах производится сравнение на больше/меньше, и в результате получается направление "углубления в дерево", поэтому в узлах не ключи, а информация для принятия решения при поиске.


Это то я понимаю . Непонимаю одного.
Допустим страница вмещает 500 ключей . А у одного из ключей допустим 20 тысяч значений. Ключ то поместится на странице. Но куда значения складываются в самой базе. Надо ж куда то положить 20 тысяч значений rowid по данному ключу )
Вот соответственно и хочется понять где что postgre что другие базы будут хранить эти 20 тысяч значений ключа .
Вопрос да, не по программированию как таковому. Вопрос скорее по либо postgre либо по fb
20 май 19, 13:50    [21888866]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Значения хранятся в таблице.

В индексе (оно-же B+Tree) хранятся только пары (key,rowid).

Для Оракла существует дополнительная опция т.н. Index Organized Table (IOT), там в листовых вершинах
лежат значения но подобная реализация накладывает сходу ограничания на макс. длину строки такой
таблицы. Технически точно я не помню надо смотреть доки.

Как в Postgres - я не знаю т.к. не специалист но 99% что индексная структура будет подобной.
Она вообще почти во всех DBMS не сильно отличается.
20 май 19, 14:01    [21888890]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
OoCc
Member

Откуда: с Кавказа
Сообщений: 1807
sergq
alex55555
пропущено...

Гугли про двоичные деревья, для начала.

В узлах производится сравнение на больше/меньше, и в результате получается направление "углубления в дерево", поэтому в узлах не ключи, а информация для принятия решения при поиске.


Это то я понимаю . Непонимаю одного.
Допустим страница вмещает 500 ключей . А у одного из ключей допустим 20 тысяч значений. Ключ то поместится на странице. Но куда значения складываются в самой базе. Надо ж куда то положить 20 тысяч значений rowid по данному ключу )
Вот соответственно и хочется понять где что postgre что другие базы будут хранить эти 20 тысяч значений ключа .
Вопрос да, не по программированию как таковому. Вопрос скорее по либо postgre либо по fb

цепочка страничек. так же как и если бы одно значение не помешалось на страничку.
20 май 19, 14:05    [21888893]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48132
sergq
Допустим страница вмещает 500 ключей

Если всё множество rowid для одного ключа не умещается на одну страницу - его хвост выпихнут на другие страницы с этим же ключом.
21 май 19, 13:48    [21889710]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
Partisan M
Member

Откуда:
Сообщений: 1359
alex55555
Гугли про двоичные деревья, для начала.


btree не является двоичным деревом. Неохота комментировать всё, что тут понаписали. Но автору вопроса действительно быстрее было бы найти описание структуры btree поиском в google.
21 май 19, 15:17    [21889808]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7827
Кнут
Том 3. Сортировка и поиск
https://www.ozon.ru/context/detail/id/2527036/
21 май 19, 15:20    [21889811]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Вы оба правы. В данном случае автор спрашивает по блочно-организованной структуре данных
https://en.wikipedia.org/wiki/B _tree которая используется в БД. В качестве пруфа, он указывает rowid.
Это чисто базячная терминология.

Но бинарное дерево https://en.wikipedia.org/wiki/Binary_tree это теоретический прародитель Дерева с плюсом+ N-го
порядка если соптимизировать хранение бинарных нод в блок но при этом сохранить исходящие связи.
21 май 19, 15:54    [21889849]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
alex55555
Member

Откуда:
Сообщений: 2129
Partisan M
btree не является двоичным деревом.

Двоичное есть частный случай b. Ну и принцип идентичный.
22 май 19, 15:55    [21890918]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7827
Мне кажется идея смешивать в одну кучу бинарные деревьев и b-tree - не из лучших
Больше путаницы, чем смысла
Дополнительную и большую путаницу вносить сокрашение. Т.к. предполагаешь, что b-tree это сокрашение от binary, а на самом деле, это _отдельная_ структура.

Т.ч. проще считать, что B-Tree это - B-Tree, а бинарное дерево - это бинарное дерево. А совпадение в первой буквы - это происки врагов человечества, что бы всех запутать.

IMHO & AFAIK
22 май 19, 16:04    [21890932]     Ответить | Цитировать Сообщить модератору
 Re: Btree значения  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Leonid Kudryavtsev,

обычно говорят что
автор
A red/black tree is more or less equivalent to a 2-3-4 tree, which is just a type of B-tree

и не будет никакой путаницы
23 май 19, 08:30    [21891443]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить