Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5 6 7 8 9 10 11   вперед  Ctrl      все
 Re: Слабые стороны Cache & SQL  [new]
ChA
Member

Откуда: Москва
Сообщений: 11383
Iura
Вот именно почитай.
Читаю, Вы продолжаете нести бред, смешивая в кучу умные слова. Может пора остановиться и заняться делом ?

Удачи.
17 май 06, 16:18    [2675185]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Andreww
Member [заблокирован]

Откуда:
Сообщений: 1752
2 pgres

Такая структура (данные только в листах) называется B+ или B* деревом, и именно она используется на практике, почему-то часто этот * или + опускают (я кстати стараюсь не опускать) видимо считая, что практически Bдерево может быть реализованно только как B+ :).

Читайте внимательнее мой изначальный пост к lura (https://www.sql.ru/forum/actualthread.aspx?bid=10&tid=293038&pg=3#2673227) я в нём говорю про B*, а вы уже отвечаете про "...в IOT не хранятся данные в В-дереве...".
17 май 06, 16:29    [2675248]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Iura
Member

Откуда:
Сообщений: 138
mir
Iura
Любая информация занимает место. Не важно она полезная или нет. Важно другое, когда ты начинаешь искать то что тебе нужно, тебе приходится просматривать и ненужную инфо тоже. Причем тем чаще, чем длинее файл. Индекс тебе указывает номер страницы в которой находится нужная информация, но не конкретный row И не тем более конкретный физический адрес на hard disk. Сервак полностью просматривает страницу на которую указывает индекс.

Дополнительно. Сами индексы занимают кчу места и имеют сложную иерархию. Чтобы в самом индексе найти нужную конечну "ветку + лист" нужно немного потрудится. И чем длинее файл тем болеьше надо трудится. Ведь индекс в память полностью не загружается. Да возможно для того чтобы ему дойти до последней ветки нужно сделать не более 10-50 if, но эти же значения разбросанны на диске и причем не эффективно. Поэтому опять возникнет нагрузка на файл и диск. А если это многопользовательская система ? а если еще там isolations куча, тогда что.
Уважаемый Iura. По вашему посту видно, что вы очень плохо знакомы с технологией организацией индексного поиска в БД. Советую некоторое время посвятить чтению.



http://msdn2.microsoft.com/en-us/library/ms190969(d=ide).aspx
http://msdn2.microsoft.com/en-us/library/ms188270(d=ide).aspx
http://msdn2.microsoft.com/en-us/library/ms177443(d=ide).aspx
http://msdn2.microsoft.com/en-us/library/ms177484(d=ide).aspx
17 май 06, 16:37    [2675303]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
pgres
Member

Откуда: Харьков
Сообщений: 140

Iura уволь сибя сам
какую траву ты куришь поделись

есть такой психологический тест "понимание при чтении"
так вот даже и не пробуй его сдавать

Это все еще актуально

2 Andreww
Я прошу прощения. буду знать

--
Кто - еще до сражения - побеждает предварительным расчетом , у того шансов много (Сунь Цзы)
17 май 06, 16:46    [2675370]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
SiDen
Member

Откуда:
Сообщений: 518
To lura:
имхо вы несколько заблуждаетесь, например, есть первая страница хранения индекса, в конце нее стоит линк на следующую страницу, и так далее (при чем список двунаправлен), читать левые(чужие, пустые) страницы никто не будет вне зависимости от того сколько там их пустых.
такая же штука с данными + имеются страницы, где хранится информация о том какие страницы свободны, а какие нет, на сколько заполнены эти страницы в дискретном процентном соотношении (0-50,51-80,81-95,96-100)
вероятно такие фичи как упреждающее чтение и прочее влияют на процесс чтения при близком расположении нужных страниц, но это нужно тестировать.
17 май 06, 17:22    [2675698]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Iura
Member

Откуда:
Сообщений: 138
Перечитал доку по новой.

Признаю, в чем-то был не прав.
17 май 06, 17:59    [2675969]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
Andreww
Говорит только о том, что либо в М(КАШЕ) какой-то НОВЫЙ и довольно сложный алгоритм, либо вы слабо владеете предметом, т.к. при вставке значительного числа элементов в B*дерево узлы будут быстро заполняться и часто требуется расшепление всех родительских вершин вплоть до корня,что в многопользовательской среде приводит к блокированию значительной части дерева (а никак не НЕСКОЛЬКИХ блоков), кроме того помимо расщепления есть ещё и слияние блоков (что бы не тратить зря место) тоже не самая быстрая операция.
других алгоритмов я не знаю, потому и прошу поделиться.

ну вот, например, физическая реализация хранения некоего двухуровневого
массива ^X(i1,i2)
блок указателей (пусть #50)
^X(1,1)=100 -> ссылка на блок данных
^X(300,10)=101
^X(555,500)=102

блок данных #100
^X(1,1)=... -> ссылка и данное при узле
^X(1,2)=...
...
(ссылка на блок #101)

блок данных #101
^X(300,10)=...
^X(300,11)=...
...
^X(555,499)=...
(ссылка на блок #102)

блок данных #102
^X(555,500)=...
...
команда
set ^X(300,10.5)=...
порождающая создание узла ^X(300,10.5) в лучшем случае приведет к смещение ссылок внутри блока #101 (для сохранения сортировки), в худшем (когда блок заполнен) к созданию нового блока (пусть #300) и помещения выпавших после сдвига ссылок в него с изменением ссылки блока #101 (со #102 на #300) и добавлением нового указателя в блок #50, который в этом случае приобретет вид:

блок указателей #50
^X(1,1)=100
^X(300,10)=101
^X(555,499)=300
^X(555,500)=102
это немножко утрированное описание, конечно, там есть свои нюансы
разбиения заполненного блока и переноса части его содержимого, но
принцип вообще-то такой.

как мы видим, изменением затрагивается либо один блок, либо два блока +
блок указателей. есть, конечно, вариант с уже полным блоком указателей.
в этом случае процедура обработки нового блока повторяется на уровне указателей (намного реже чем для данных).
при этом естественно происходит блокировка именно этих (и только этих
блоков) модулем работы с БД. задачи работающие с ^X(555,500) или
^X(1) могут ожидать только освобождения блока #50, если уж они сами
породили в процессе своей работы новый блок данных.


И кстати :) Индексы в виде B*-деревьев, существуют в Рел. системах от рождения (ещё от SYSTEM-R) :) Но это именно ИНДЕКСЫ, данные (как правило) хранятся в других структурах - почувствуйте разницу,все уже много лет как ушли от хранения ДАННЫХ в B*-дереве именно из-за того что поддерживать балланс в многопользовательской среде накладно и сложно,хотя для некоторых случаев можно и в B*-дереве хранить (в оракле например есть IOT про DB/2 MSSQL не знаю) и тут появляется М-технология и зовёт нас обратно в 70-е :)
Странно, не находите ?

будьте так добры, напомните мне систему, в которой данные ранее хранились вместе с индексами, а потом, следуя оптимальным теориям были перемещены в отдельную структуру. я вообще-то вижу нечто обратное. вот тот же IOT, например.
17 май 06, 18:12    [2676057]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
pavelvp
Member

Откуда:
Сообщений: 673
Andreww
Такая структура (данные только в листах) называется B+ или B* деревом
Не "или", а просто B+. Причём в B+дереве листья ещё и связаны между собой.
B* дерево - следующая модификация. Его особенность в улучшенном алгоритме вставки за счёт использования идеи "переливания" и сокращении количества делений узлов.
17 май 06, 18:29    [2676142]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Andreww
Member [заблокирован]

Откуда:
Сообщений: 1752
2 pavelp

Конечно так, просто недоговорил.

Хотел обратить внимание на то, что данные в листах в В+ ИЛИ В* деревьях, вроде нигде не говорил, что это одно и то же :( у В*, перелив иной, это факт и вроде как у В* листья тоже связаны.
17 май 06, 18:38    [2676183]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
pavelvp
Member

Откуда:
Сообщений: 673
Sergei Obrastsov
задачи работающие с ^X(555,500) или
^X(1) могут ожидать только освобождения блока #50, если уж они сами
породили в процессе своей работы новый блок данных.
А если не породили, то не должны ждать?
Что они будут делать, если в процессе работы других задач произойдёт деление блока #50 и увеличение уровня дерева?
Разделяемая блокировка должна накладываться в любом случае. Кто-то кого-то да должен подождать :-)
17 май 06, 18:44    [2676222]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
pavelvp
Sergei Obrastsov
задачи работающие с ^X(555,500) или
^X(1) могут ожидать только освобождения блока #50, если уж они сами
породили в процессе своей работы новый блок данных.
А если не породили, то не должны ждать?
Что они будут делать, если в процессе работы других задач произойдёт деление блока #50 и увеличение уровня дерева?
Разделяемая блокировка должна накладываться в любом случае. Кто-то кого-то да должен подождать :-)

а кто спорит? только блокировка накладывается на затронутые изменением блоки, а не на все блоки подряд.
когда изменится блок указателей, то его разблокировки будут ждать все те задачи, которые получают доступ к узлам, указанным в нем, но не к узлам, указанным в предыдущем или последующем блоке указателей.
17 май 06, 18:52    [2676255]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Andreww
Member [заблокирован]

Откуда:
Сообщений: 1752
2 Sergei Obrastsov

Уффф. А надо ли комментировать...... Дерево с одним уровнем.

Посмотрите внимательнее, блок указателей у вас "бесконечный" т.к. данных мноооого или мало, но это СПИСОК указателей ведь тоже надо хранить и скорее всего на диске (т.к. вы сами заранее разбили всё хранилище на блоки) ?

Если вы настаиваете на блоке указателей ФИКСИРОВАННОГО размера (который растёт когда появляются новые блоки), то тогда БЛОКИ ДАННЫХ у вас быстро превращяются в связанные списки (т.к. вы сами заранее разбили всё хранилище на блоки) и, опять же, если данных мнооого списки будут длинююющие и поиск в них небыстрый (хотя в сортированных списках конечно искать легче, но при вставке придётся двигать).

И чего вы добились, сохранив указатели в одном списке, а данные разбросав по блокам? Уменьшили время поиска в столько раз, сколько указателей помещается в список ?

B*дерево решает проблемы поиска совсем по-другом (там размер блока фиксированный и число уровней переменное, но за это приходится платить расщеплением и слиянием).

>>будьте так добры, напомните мне систему, в которой данные ранее хранились вместе с индексами, а потом, следуя оптимальным теориям были перемещены в отдельную структуру

D3 от Rainingdata (ровесник МУ-МУ). Данные сначала хранились В ТОЧНОСТИ КАК ВЫ ОПИСАЛИ, даже размер списка указателей требует при создании ФАЙЛА, спустя некоторое время (не так давно) было добавленно отдельно живущее и автоматически поддерживаемое B*(или B+ не помню точно) дерево.
17 май 06, 19:12    [2676329]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
LittleCat
Member

Откуда: СПб
Сообщений: 435
Andreww
2 Sergei Obrastsov

Уффф. А надо ли комментировать...... Дерево с одним уровнем.

Ну зря Вы так, Сергей же просто пример привел, при разрастании дерева в М системах строится несколько уровней указателей. Размер блока указателей (да и вообще блока базы данных, с которым ведется операция как на диске, так и в кэше) является фиксированным (как впрочем и блока в котором хранятся данные). В ранних М системах этот размер был фиксированным (например в DSM-11 это был килобайт). С размером блока были связаны ограничений как на длину полной ссылки, так и на длину отдельного узла данных. С ростом потребностей (ну неудобно иметь длину локальной переменной в 32 кБ, а глобальной всего 511 байт или около того, сейчас не помню) разные производители внесли соответствующуе улучшения (в Cache блок базы сделали 8 кБ, в GT.M вообще этот параметр для базы сделали настраиваемым, можно для разных баз задать разный размер блока базы). Так что насчет уровней, торопиться не надо, тем более число индексов может быть до 63...
PS. Блоки делятся на: Блок главного каталога, Блок указателей, Блок указателей на нижний уровень (т.е. на блоки данных), и собственно блоки данных. Ну это если вкратце...
17 май 06, 20:26    [2676502]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
буржуй
Guest
все РСУБД-шники - необразованные демагоги, это факт. Просто куда ни ткни. Очередной яркий пример от Andreww:

И кстати :) Индексы в виде B*-деревьев, существуют в Рел. системах от рождения (ещё от SYSTEM-R) :) Но это именно ИНДЕКСЫ, данные (как правило) хранятся в других структурах - почувствуйте разницу,все уже много лет как ушли от хранения ДАННЫХ в B*-дереве именно из-за того что поддерживать балланс в многопользовательской среде накладно и сложно,хотя для некоторых случаев можно и в B*-дереве хранить (в оракле например есть IOT про DB/2 MSSQL не знаю) и тут появляется М-технология и зовёт нас обратно в 70-е :)
Странно, не находите ?

>>будьте так добры, напомните мне систему, в которой данные ранее хранились вместе с индексами, а потом, следуя оптимальным теориям были перемещены в отдельную структуру

D3 от Rainingdata (ровесник МУ-МУ). Данные сначала хранились В ТОЧНОСТИ КАК ВЫ ОПИСАЛИ, даже размер списка указателей требует при создании ФАЙЛА, спустя некоторое время (не так давно) было добавленно отдельно живущее и автоматически поддерживаемое B*(или B+ не помню точно) дерево.

------------

Оказывается "все" это D3, и конечно же, ничего общего с mumps у D3 нет и не было (а если и есть, то то же самое общее, что и с Oracle и т.п.).
17 май 06, 20:33    [2676520]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
Andreww

Уффф. А надо ли комментировать...... Дерево с одним уровнем.

не надо торопиться с выводами. во-первых, с двумя.
во-вторых, дерево вида ^X(i1,i2,i3,i4,i5,i6,i7) ложится в такую же структуру
блок указателей #50
^X(1,2,3,4,5,1,"xxx")=100
^X(1,2,3,4,5,555,"yyy")=101
^X("X","Y","Z",6,7,8,"kkk")=102
...

и что это я все сбалансированные деревья рисую? вот так нагляднее?

блок указателей #50
^X = 101
^X(100,255)=102
^X(160,100,400)=103
^X(500,400)=104
^X(600,101,202,303,405,7)=105
...


Посмотрите внимательнее, блок указателей у вас "бесконечный" т.к. данных мноооого или мало, но это СПИСОК указателей ведь тоже надо хранить и скорее всего на диске (т.к. вы сами заранее разбили всё хранилище на блоки) ?

а разве я не упоминал про возможность заполнения блока указателей?
конечно блок фиксирован размером, какой же это был бы иначе блок?
сейчас, скажем, 8Kb (как и блок данных и прочие другие блоки).


Если вы настаиваете на блоке указателей ФИКСИРОВАННОГО размера (который растёт когда появляются новые блоки), то тогда БЛОКИ ДАННЫХ у вас быстро превращяются в связанные списки (т.к. вы сами заранее разбили всё хранилище на блоки) и, опять же, если данных мнооого списки будут длинююющие и поиск в них небыстрый (хотя в сортированных списках конечно искать легче, но при вставке придётся двигать).

а ведь очевидно, что поиск идет через блоки указателей, а не через
всю цепочку блоков данных. или нет? блоки указателей тоже растут
по мере роста блоков данных, хоть и не так быстро. вот скажем массив
с 162 млн. узлов занимает 366,061 блоков данных, 515 блоков указателей 2-го уровня и один блок указателей 1-го уровня. (ага, все тот же, из сравнения)


И чего вы добились, сохранив указатели в одном списке, а данные разбросав по блокам? Уменьшили время поиска в столько раз, сколько указателей помещается в список ?

я вообще-то ничего не добивался, я просто показал как хранятся данные.
в ответ на соответствующий вопрос. время поиска сокращается очень значительно, иначе бы эти структуры не использовались.
и не только в M, ага. :)


B*дерево решает проблемы поиска совсем по-другом (там размер блока фиксированный и число уровней переменное, но за это приходится платить расщеплением и слиянием).

вот странно, а все полагают, что это оно и есть.


D3 от Rainingdata (ровесник МУ-МУ). Данные сначала хранились В ТОЧНОСТИ КАК ВЫ ОПИСАЛИ, даже размер списка указателей требует при создании ФАЙЛА, спустя некоторое время (не так давно) было добавленно отдельно живущее и автоматически поддерживаемое B*(или B+ не помню точно) дерево.

данные там и сейчас хранятся так же как и раньше, в итемах и файлах.
и откуда, интересно, информация про "В ТОЧНОСТИ ТАК..."?
раньше использовали hash-indexing, потом добавили
B-tree, молодцы, растут.
17 май 06, 20:38    [2676532]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Andreww
Member [заблокирован]

Откуда:
Сообщений: 1752
2 Sergei Obrastsov

>>не надо торопиться с выводами. во-первых, с двумя.

Определение уровня у вас своё ? Корень дерева имеет уровень 0, любой другой узел имеет уровень на 1 больше потомка (определение всех остальных людей).

У вас в примере который вы привели (УКАЗАТЕЛИ) -> (БЛОКИ ДАННЫХ), сл-но глубина вашего дерева равна 1 и список указателей всегда показывает на данные, сл-но дерево у вас с 1 уровнем.

>>конечно блок фиксирован размером, какой же это был бы иначе блок?

мало-ли какой, вон уровень у вас "не как у людей" :)

>>сейчас, скажем, 8Kb (как и блок данных и прочие другие блоки).

Хммм. А менять размер можно ? Для указателей 8к может и нормально (хотя надо учитывать что при вставке\удалении указатели двигать надо), но для данных перебор.

>>а ведь очевидно, что поиск идет через блоки указателей, а не через всю цепочку блоков данных. или нет? блоки указателей тоже растут

Пару минут назад я думал что "блок фиксирован размером, какой же это был бы иначе блок" теперь выясняем, что "растут подлецы" :)

А указатель-то на блок данных в списке указателей надо найти ? Или как ?

Вот ваш же пример

блок указателей #50
^X = 101
^X(100,255)=102
^X(160,100,400)=103
^X(500,400)=104
^X(600,101,202,303,405,7)=105
....... и далее

Как мне найти номер блока данных для ^X(230,67,22,3,87,11,55,3,223) ? Есть он вообше в 8 килобайтах блока #50 или блок #50 уже вырос или .... ?

Вообше, если операция проекции для вас понятна, лучше перейти от невнятных размерностей к 1-мерному пространству, будет понятнее (тем более в машине всё так и храниться).

>>массив 162 млн. узлов занимает 366,061 блоков данных, 515 блоков указателей 2-го уровня и один блок указателей 1-го уровня.

Стоп-стоп. В исходном примере у вас блок указателей показывал только на данные, теперь оказывается есть ещё уровень указателей, т.е. дерево всё-таки глубины 2 или может 3 или всё же не ограничено ?
Обясните.

>>время поиска сокращается очень значительно, иначе бы эти структуры не использовались.и не только в M, ага. :)

Так дело в том что "не только в М" у дерева глубина произвольная и поиск потому эффективнее.

>>вот странно, а все полагают, что это оно и есть.

Не знаю кто "все", но в Б*дереве глубина не ограничена 2 уровнями. Несогласны ?

>>раньше использовали hash-indexing,

Вообще-то ХЭШ-СПИСОК, ну да ладно, смысл от этого не меняется, сначала находим указатель на СПИСОК (по хэшу) (из списка указателей) потом последовательным перебором этого списка находим нужный нам элемент.

Как и у вас - 1 уровень (кстати убыстрен за счёт ХЭША, а как у вас пока не понятно) второй уровень- последовательный перебор списка до нужного элемента (ИТЕМА как вы говорите).

Файл с 40 милионнами "ИТЕМОВ" умирает, т.к. хэш-функция есс-но неполная то скорость выборки пропорциональна размеру файла.


2 буржуй

Просили напомнить, я напомнил, а если нечего сказать лучше жевать. рябчиков например.

2 LittleCat

>>Ну зря Вы так, Сергей же просто пример привел, при разрастании дерева в М системах строится несколько уровней указателей.

Несколько это 2,3,5 ? Может я горячусь и там разумное ограничение эдак в 100-200 уровней ?
Почему никто не может объяснить ?
Зачем вообще это ограничивать 2 или 3 уровнями ? Нормальное Б*дерево всегда будет эффективнее для поиска,
а 3 или 5 уровней вызовут все те же проблемы расщепления-слияния (блокировка блоков указателей до корня) про которые уже всё рассказали.


>>Размер блока указателей (да и вообще блока базы данных, с которым ведется операция как на диске, так и в кэше)
>>С размером блока были связаны ограничений как на длину полной ссылки, так и на длину отдельного узла данных.


Вы очевидную вешь "блока базы данных, с которым ведется операция как на диске, так и в кэше" полагаете чем то особенным именно для М-систем ?
Если нет зачем про это писать ?
У кого работа с блоками ведётся по-другому ?

>>С ростом потребностей (ну неудобно иметь длину локальной переменной в 32 кБ, а глобальной всего 511 байт или около того, сейчас не помню) разные производители внесли соответствующуе улучшения (в Cache блок базы сделали 8 кБ, в GT.M вообще этот параметр для базы сделали настраиваемым, можно для разных баз задать разный размер блока базы).

Вы всерьёз полагаете простое увеличение "улучшением" ?
Кто-то тут говорил какая КАШЕ супре экономная и вдруг такое улучшение :(
А GT.M давно появилась ? Почему только там догадались сделать параметр настраиваемым ?


>> Так что насчет уровней, торопиться не надо, тем более число индексов может быть до 63...

Как связано число уровней в Б*дереве и число индексов ?
17 май 06, 22:39    [2676682]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
c127
Guest
LittleCat
c127

Это понятно, когда ничего кроме кеша не знаешь, то кажется что все что есть в мире - взято из кеша.

Не все в мире взято из кеша, а просто современные базы данных пришли к тому, что в М технологиях существовало от их рождения, с далеких 60-х ;-) (Я про B* деревья)

Деревья не изобретение КЕШ-а. Запатентуйте еще блок питания и постоянный ток.
Данные в РСУБД (по-видимому это они понимаются под именем "современные базы данных") хранятся в таблицах, которые есть отношения. Как было у Кодда в самом начале, так и осталось, никто никуда не пришел. А индексы - это средство, вопрос удобства и вряд ли их взяли из КЕШ-а.



Iura

Вот именно почитай.

Любая информация занимает место. Не важно она полезная или нет. Важно другое, когда ты начинаешь искать то что тебе нужно, тебе приходится просматривать и ненужную инфо тоже. Причем тем чаще, чем длинее файл.

Не приходится. На устройстве прямого доступа можно перейти на заданный сектор (страницу) без прохода по промежуточным. Это Вы перепутали с ленточным устройством, которое последовательного доступа. Ненужные данные читаются всегда, существует минимальная порция считывания с диска, сектор по-моему, меньше него железо прочитать физически не в состоянии. Но ненужные сектора не читаются, даже если они принадлежат тому же файлу.

Iura

Так кто нибудь пусть ответит на мой вопрос.
Значит производительность никак не зависит от размера фалов и используемого пространства ?

Отвечаю: не зависит никак. Связи размера файла БД современного СКЛ сервера с производительностью нет.

К тому же, повторяю еще раз, при обычной работе файлы растут не так быстро.

Iura

Дополнительно. Сами индексы занимают кчу места и имеют сложную иерархию.

Не кучу, гораздо меньше чем данные, но безусловно занимают. А что, в КЕШ-е индексы места вообще не занимают? Иерархия деревьев в КЕШ-е тоже сложная.

Мы выяснили в соседнем топике что в М, например, индексы отсутсвуют в принципе. Вместо них предлагается ДУБЛИРОВАТЬ ДАННЫЕ в деревья подходящей структуры. Вот это действительно КУЧА места. Место под индексы по сравнению с этим - детские шалости.

Iura
Чтобы в самом индексе найти нужную конечну "ветку + лист" нужно немного потрудится. И чем длинее файл тем болеьше надо трудится. Ведь индекс в память полностью не загружается. Да возможно для того чтобы ему дойти до последней ветки нужно сделать не более 10-50 if,

Опять чепуха. Есть хеш индексы, поиск в них - константа, не зависит ни от чего, только от начальной конфигурации.

Iura
но эти же значения разбросанны на диске и причем не эффективно.

Как файл расположен на диске - проблема операционной системы. КЕШ ведь тоже не сама рассовывает файлы по секторам и дорожкам. Как показывает опыт ничего страшного на больших файлах не происходит. Кластерные индексы определенные не к месту убивают базу гораздо быстрее, чем размер файла.

Не упорствуйте, чем дольше Вы пытаетесь выкрутиться, тем глубже закапываетесь и тем комичнее это выглядит. Признайте что ошиблись.
18 май 06, 00:22    [2676822]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
Andreww
Определение уровня у вас своё ? Корень дерева имеет уровень 0, любой другой узел имеет уровень на 1 больше потомка (определение всех остальных людей).
У вас в примере который вы привели (УКАЗАТЕЛИ) -> (БЛОКИ ДАННЫХ), сл-но глубина вашего дерева равна 1 и список указателей всегда показывает на данные, сл-но дерево у вас с 1 уровнем.

корнем для блока указателей является блок каталога, ну да ладно

Andreww

>>сейчас, скажем, 8Kb (как и блок данных и прочие другие блоки).
Хммм. А менять размер можно ? Для указателей 8к может и нормально (хотя надо учитывать что при вставке\удалении указатели двигать надо), но для данных перебор.

на длинных данных используются какие-то свои хитрости, я пока не ковырялся,
но понятие big-string у них существует. наверное указатель


>>а ведь очевидно, что поиск идет через блоки указателей, а не через всю цепочку блоков данных. или нет? блоки указателей тоже растут
Пару минут назад я думал что "блок фиксирован размером, какой же это был бы иначе блок" теперь выясняем, что "растут подлецы" :)

"растут" не в размерах, а в количестве.


А указатель-то на блок данных в списке указателей надо найти ? Или как ?
Вот ваш же пример

блок указателей #50
^X = 101
^X(100,255)=102
^X(160,100,400)=103
^X(500,400)=104
^X(600,101,202,303,405,7)=105
....... и далее

Как мне найти номер блока данных для ^X(230,67,22,3,87,11,55,3,223) ? Есть он вообше в 8 килобайтах блока #50 или блок #50 уже вырос или .... ?

а вот насчет поиска - это уже не ко мне. алгоритмы бывают разные, а
система вовсе не Open Source. понятно, что блоки указателей тоже
выстраиваются в цепочку. когда она становится слишком большой,
добавляется уровень указателей выше. добавится ли новый уровень,
когда и тот заполнится - не знаю, у меня нет БД такого большого объема.


>>массив 162 млн. узлов занимает 366,061 блоков данных, 515 блоков указателей 2-го уровня и один блок указателей 1-го уровня.
Стоп-стоп. В исходном примере у вас блок указателей показывал только на данные, теперь оказывается есть ещё уровень указателей, т.е. дерево всё-таки глубины 2 или может 3 или всё же не ограничено ?
Обясните.

может все-таки не стоит додумывать за меня то, что я не говорил?
разве я что-нибудь писал про ограничения?


>>время поиска сокращается очень значительно, иначе бы эти структуры не использовались.и не только в M, ага. :)
Так дело в том что "не только в М" у дерева глубина произвольная и поиск потому эффективнее.

а разве я спорю? B-деревья - вещь удобная. и B-деревья вовсе
не изобретение M-технологии, как пытаются за нас утверждать некоторые.


>>вот странно, а все полагают, что это оно и есть.
Не знаю кто "все", но в Б*дереве глубина не ограничена 2 уровнями. Несогласны ?

а разве я писал про ограничения?


>>раньше использовали hash-indexing,
Вообще-то ХЭШ-СПИСОК, ну да ладно, смысл от этого не меняется, сначала находим указатель на СПИСОК (по хэшу) (из списка указателей) потом последовательным перебором этого списка находим нужный нам элемент.
Как и у вас - 1 уровень (кстати убыстрен за счёт ХЭША, а как у вас пока не понятно) второй уровень- последовательный перебор списка до нужного элемента (ИТЕМА как вы говорите).

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


>>Ну зря Вы так, Сергей же просто пример привел, при разрастании дерева в М системах строится несколько уровней указателей.
Несколько это 2,3,5 ? Может я горячусь и там разумное ограничение эдак в 100-200 уровней ?
Почему никто не может объяснить ?

послушайте, может Вы можете нам объяснить как это будет выглядить
в IOT на террабайте данных? я с удовольствием послушаю. а то как-то
некрасиво получается, что Вам не скажи - все мало.

может и нет там ограничений вовсе? нет, ограничение конечно есть - 32Tb
на размер БД, то есть блок в БД адресуется 4-мя байтами. и все это
укладывается в 3 уровня (2 уровня указателей и уровень данных).


Зачем вообще это ограничивать 2 или 3 уровнями ? Нормальное Б*дерево всегда будет эффективнее для поиска,
а 3 или 5 уровней вызовут все те же проблемы расщепления-слияния (блокировка блоков указателей до корня) про которые уже всё рассказали.

значит необходимости в увеличении размерности дерева нет. я не думаю,
что там сидят глупые люди, которые за 40 лет ничего больше придумать
не смогли.


Вы всерьёз полагаете простое увеличение "улучшением" ?
Кто-то тут говорил какая КАШЕ супре экономная и вдруг такое улучшение :(
А GT.M давно появилась ? Почему только там догадались сделать параметр настраиваемым ?

в Cache он тоже настраиваемый (в своем роде, 2Kb или 8Kb). вот потому и
"экономная", что долго тянули с этим выбором. или нужно объяснять чем
невыгоден большой разбер блока на небольших данных?


>> Так что насчет уровней, торопиться не надо, тем более число индексов может быть до 63...
Как связано число уровней в Б*дереве и число индексов ?

а никак. связано только количество узлов с данными.

я вот вижу, что B-дерево увидели только в способе хранения.
а то, что хранится тоже дерево - нет.
18 май 06, 03:30    [2676930]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
c127
Деревья не изобретение КЕШ-а. Запатентуйте еще блок питания и постоянный ток.
Данные в РСУБД (по-видимому это они понимаются под именем "современные базы данных") хранятся в таблицах, которые есть отношения. Как было у Кодда в самом начале, так и осталось, никто никуда не пришел. А индексы - это средство, вопрос удобства и вряд ли их взяли из КЕШ-а.

Cache здесь, честно говоря, вообще не причем. речь идет о M-технологии.
ну конечно, не разработчики M изобрели B-дерево и вообще иерархические структуры. но они оценили и взяли их на вооружение еще тогда, в 70-х. как
видим, они оказались дальновидны. а ведь все очень просто, с большими
объемами данных первыми столкнулись именно они.


Не приходится. На устройстве прямого доступа можно перейти на заданный сектор (страницу) без прохода по промежуточным. Это Вы перепутали с ленточным устройством, которое последовательного доступа. Ненужные данные читаются всегда, существует минимальная порция считывания с диска, сектор по-моему, меньше него железо прочитать физически не в состоянии. Но ненужные сектора не читаются, даже если они принадлежат тому же файлу.

приходится. над физическое размещение файла наложена его логическая
структура, которая ну никак в секторы по 512 байт не укладывается.
об этом Вам и говорят. вот тот же блок в 8Kb, например.


Iura

Дополнительно. Сами индексы занимают кчу места и имеют сложную иерархию.

Не кучу, гораздо меньше чем данные, но безусловно занимают. А что, в КЕШ-е индексы места вообще не занимают? Иерархия деревьев в КЕШ-е тоже сложная.
Мы выяснили в соседнем топике что в М, например, индексы отсутсвуют в принципе. Вместо них предлагается ДУБЛИРОВАТЬ ДАННЫЕ в деревья подходящей структуры. Вот это действительно КУЧА места. Место под индексы по сравнению с этим - детские шалости.

как мы уже заметили в "соседнем топике", наличие этого дублирования
почему-то не занимает КУЧУ места, а занимает объем гораздо меньший,
чем прекрасно организованные индексы в SQL. можем повторить опыт,
если есть желание. :)


Iura
Чтобы в самом индексе найти нужную конечну "ветку + лист" нужно немного потрудится. И чем длинее файл тем болеьше надо трудится. Ведь индекс в память полностью не загружается. Да возможно для того чтобы ему дойти до последней ветки нужно сделать не более 10-50 if,

Опять чепуха. Есть хеш индексы, поиск в них - константа, не зависит ни от чего, только от начальной конфигурации.

ну да, головки ведь у дисков мгновенного действия, позиционирования нынче
не существует, индексный файл прекрасно влезает в память...


Как файл расположен на диске - проблема операционной системы. КЕШ ведь тоже не сама рассовывает файлы по секторам и дорожкам. Как показывает опыт ничего страшного на больших файлах не происходит. Кластерные индексы определенные не к месту убивают базу гораздо быстрее, чем размер файла.

"операционной системе" пофигу сколько времени нужно задаче на собирание
вместе кусков файла БД. а вот задаче - нет. дефрагментация всегда давала
выигрыш в скорости, дает и сейчас, даже при наличии "супер-файловых" систем.
18 май 06, 03:58    [2676944]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
pavelvp
Member

Откуда:
Сообщений: 673
to Andreww & c127
Ребята, вы что-то заговариваться стали...

to Sergei Obrastsov
может и нет там ограничений вовсе? нет, ограничение конечно есть - 32Tb
на размер БД, то есть блок в БД адресуется 4-мя байтами. и все это
укладывается в 3 уровня (2 уровня указателей и уровень данных).

Никак не может такого быть. Страница 8К, следовательно порядок дерева около 500 (реально возможно и меньше). Дерево такого порядка при размере 32Т будет, как минимум, 4-х уровневое. А то и пяти...
я вот вижу, что B-дерево увидели только в способе хранения.
а то, что хранится тоже дерево - нет.
В-дереву по барабану что в нём хранят :-) Точно такой же индекс можно и в реляционке организовать.
18 май 06, 13:05    [2678634]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
pavelvp

to Sergei Obrastsov
может и нет там ограничений вовсе? нет, ограничение конечно есть - 32Tb
на размер БД, то есть блок в БД адресуется 4-мя байтами. и все это
укладывается в 3 уровня (2 уровня указателей и уровень данных).

Никак не может такого быть. Страница 8К, следовательно порядок дерева около 500 (реально возможно и меньше). Дерево такого порядка при размере 32Т будет, как минимум, 4-х уровневое. А то и пяти...

нет фактических типов промежуточных блоков указателей, только TOP и
BOTTOM. впрочем, может они ими извращаются? не знаю, как только найду
такую базу - сразу посмотрю.

pavelvp

я вот вижу, что B-дерево увидели только в способе хранения.
а то, что хранится тоже дерево - нет.
В-дереву по барабану что в нём хранят :-) Точно такой же индекс можно и в реляционке организовать.

правильно, по барабану. но мне-то нет. :)
это не индекс, это ВСЯ структура.

C уважением. Сергей
18 май 06, 13:35    [2678868]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Andreww
Member [заблокирован]

Откуда:
Сообщений: 1752
2 pavelp

>> Ребята, вы что-то заговариваться стали...

Полагаете пора ликбез закончить ? Пожалуй.

2 Sergei Obrastsov

>>корнем для блока указателей является блок каталога, ну да ладно

:( Вы читаете что вам пишут или нет ?

Ещё раз : Корень дерева имеет уровень 0, любой другой узел имеет уровень на 1 больше потомка (определение всех остальных людей).

Корень ВАШЕГО дерева, это и есть "самый первый" блок указателей.


>>"растут" не в размерах, а в количестве.

Я про это и говорю.


>>а вот насчет поиска - это уже не ко мне. алгоритмы бывают разные, а
>>система вовсе не Open Source. понятно, что блоки указателей тоже
>>выстраиваются в цепочку. когда она становится слишком большой,
>>добавляется уровень указателей выше. добавится ли новый уровень,
>.когда и тот заполнится - не знаю, у меня нет БД такого большого объема.

Ну я про то и говорю, и в этом списке (8 килобайтном) надо найти элемент. Если у вас 2-х уровневое дерево, надо пробежать 2 * 8 = 16 кб элементов для поиска каждого значения, в сортированном списке это сделать проще конечно :)


>>может все-таки не стоит додумывать за меня то, что я не говорил?
>>разве я что-нибудь писал про ограничения?

Сейчас сейчас всё будет.


>>а разве я спорю? B-деревья - вещь удобная. и B-деревья вовсе
>>не изобретение M-технологии, как пытаются за нас утверждать некоторые.

И кстати говоря не единственное, у оракла, например, индексы бывают :

B*tree indexes
B*tree cluster indexes
hash cluster indexes
reverse key indexes
bitmap indexes


>>а разве я писал про ограничения?

А то как же ?


>>послушайте, может Вы можете нам объяснить как это будет выглядить в IOT на террабайте данных? я с удовольствием послушаю. а то как-то
некрасиво получается, что Вам не скажи - все мало.

Нету в обычных базах IOT-ов на террабайты, о чём я и пытаюсь вам сказать, исключения бывают, но это не мой случай :)

Вот кусочек с металинка :

B*Tree Balancing
~~~~~~~~~~~~~~~~
Oracle indexes are implemented as B* Trees which are always balanced.

In an Oracle B*tree the root of the tree is at level 0. In a very small B*tree
the root block can also be a Leaf block.

In most cases, blocks on levels 0 through N-2 (where N is the height of the
tree) are Branch blocks. Branch blocks do not contain data, they simply contain
separators which are used to navigate from the root block to the the Leaf
blocks.

All Leaf blocks are at level N-1 in Oracle B*trees. All data stored in a B*tree
is stored in the Leaf blocks.

The definition of a 'Balanced Tree' is that all the data is on the same level.
Which means that the path to all data in the tree is the same length. Since all
the data is stored in Leaf blocks and all the Leaf blocks are on the same level
the B*trees are always balanced. There is no way to unbalance a B* tree.

Про ограничение на N не нашел, вполне может быть что плохо искал.

Вам раз 5 уже повторили, что при большом количестве данных и значительной глубине, механизм блокировок узлов, довольно затратный, потому террабайты и не хранят в деревьях.


По этому вопросу, работ немало - http://www.cs.wisc.edu/~cs764-1/blink.pdf, посмотрите как там его (дерево разнесчастное) крутят, и дополнительные связи вводят
и Красно-чёрные деревья добавляют и т.д. и т.п.

С того же металинка :


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The reason for doing this is that, when data is inserted into a Leaf block, and
there is no room for the insert, a very expensive operation called a split
occurs. The split creates a new Leaf block and possibly new Branch blocks as
well to maintain the balance of the tree. The split operation is by far the
most expensive operation that is done in the maintenance of B* trees so we go
to great lengths to avoid them. By not collapsing the now unused levels out of
the B*Trees after large deletes these levels (with splits) do not have to be
recreated during future inserts.


>>значит необходимости в увеличении размерности дерева нет. я не думаю,
>>что там сидят глупые люди, которые за 40 лет ничего больше придумать не смогли.

Ну вот, что это как не ОГРАНИЧЕНИЕ, то оно есть, то его нету ....




>> Так что насчет уровней, торопиться не надо, тем более число индексов может быть до 63...
Как связано число уровней в Б*дереве и число индексов ?

а никак. связано только количество узлов с данными.

А зачем тогда вспоминать про число индексов ?
18 май 06, 14:20    [2679236]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
pavelvp
Member

Откуда:
Сообщений: 673
Sergei Obrastsov
нет фактических типов промежуточных блоков указателей, только TOP и
BOTTOM. впрочем, может они ими извращаются?
Да причём тут типы. Их то как раз два - узлы и листья :-)
С 8-ми килобайтной страницей никак такое дерево не влезет в три уровня...

Sergei Obrastsov
правильно, по барабану. но мне-то нет. :)
это не индекс, это ВСЯ структура.
Да какая разница!? Точно такую же логическую структуру хранения данных в виде дерева, или как вы их назваете красиво - многомерные разреженные массивы :-), можно хранить и в реляционке (в любой РСУБД). Физически будет отличаться только тем, что данные в узлах лежат отдельно от индексов. Логически - ничем абсолютно.
18 май 06, 14:29    [2679318]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
А вот кстати вопрос кешевцам.

Как уже вами не раз упомяналось типизации нет, числа хранятся строчками и следовательно "2" будет больше чем "111".

Значит ли это что фактически для чисел можно использовать только запросы где есть точное сравнение? Т.е. запросы типа i between 2 and 111 или просто i>2 использовать нельзя
Если я не прав то объясните как это решается

Имеется ввиду конечно использование индексного поиска
18 май 06, 16:01    [2679908]     Ответить | Цитировать Сообщить модератору
 Re: Слабые стороны Cache & SQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
SergSuper
А вот кстати вопрос кешевцам.

Как уже вами не раз упомяналось типизации нет, числа хранятся строчками и следовательно "2" будет больше чем "111".

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


Значит ли это что фактически для чисел можно использовать только запросы где есть точное сравнение? Т.е. запросы типа i between 2 and 111 или просто i>2 использовать нельзя
Если я не прав то объясните как это решается
Имеется ввиду конечно использование индексного поиска

надо полагать вопрос к народу, занимающемуся Cache-SQL? я работаю
с массивами напрямую.
18 май 06, 16:16    [2679990]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5 6 7 8 9 10 11   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить