Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 17 18 19 20 21 [22] 23 24 25 26 .. 106   вперед  Ctrl
 Re: CACHE и MSSQL  [new]
Зл0й
Member

Откуда: Северная Калифорния
Сообщений: 686
andsm

неправда Ваша - на физическом уровне все СУБД используют поиск по b-tree, в т.ч. и M-системы. Таким образом итераций будет 0< i <= log2(N)


B-tree - это не бинарное дерево.
Количество итераций будет: 0< i <= log_k(N)
где k - среднее количество значений индекса на одной странице данных.[/quot]

Двоичные деревья бывают разные, в различных учебниках по computer science терминология может слекга отличаться. В Oracle и реляционных СУБД используются сбаланисированные по высоте двоичные деревья. В них время поиска-вставки-удаления элемента O(log(n)). Время "обхода по порядку" дерева - O(n).
9 ноя 06, 02:44    [3372475]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
c127
Guest
Rus000
c127
Rus000
мда, что-то скучно действительно стало в этой ветке ... неужели все обсудили? :)

Оппоненты разбежались, наверное таки решили заняться ликбезом и читают книжки.

Как поживает ООП решение задачи с билетами?

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

Да никаких проблем, бывает. Иинтересно посмотреть, так что не забудьте по возможности.

kvasov
То есть при любых индексах и ключах ораклу нужно с десяток логических поисковых прыжков, тогда как Cache нужен 1 логический шаг – СчитатьЗапись(650).


А откуда стало известно, что интересующий нас объект "Вася Пупкин" имеет адрес 650?

Gluk (Kazan)

Шо в CACHE шо в Oracle (IOT) используются одни и те же B-деревья (наверняка с некоторыми незначительными вариациями). Время поиска в них логарифмическое, но никак не константное.
Кстати, начиная с 8i в Oracle можно строить дополнительные индексы.

Что до константного времени поиска, оно в Oracle таки тоже возможно.
По ROWID


У хеш индексов по-моему константное время поиска. В оракле 8i вроде бы были хеш индексы.
9 ноя 06, 03:31    [3372490]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
###
Member

Откуда: Курумоч
Сообщений: 658
Зл0й
andsm

B-tree - это не бинарное дерево.
Количество итераций будет: 0< i <= log_k(N)
где k - среднее количество значений индекса на одной странице данных.
Двоичные деревья бывают разные, в различных учебниках по computer science терминология может слекга отличаться. В Oracle и реляционных СУБД используются сбаланисированные по высоте двоичные деревья. В них время поиска-вставки-удаления элемента O(log(n)). Время "обхода по порядку" дерева - O(n).
Повторю вслед за andsm: "B-tree - это не бинарное дерево"!!!
И терминология в данном вопросе вполне устоявшаяся... А ежели Вам не повезло с учебниками - сочуствую...

Не знаю про Oracle (при его разнообразии индексов там может быть все что угодно ), но вот цитатка из BOL по Sybase ASA 9:
"Adaptive Server Anywhere supports two types of index, and automatically chooses between them depending on the declared width of the indexed columns. For a total column width that is less than 10 bytes, Adaptive Server Anywhere uses a B-tree index that contains an order-preserving encoding, or hash value, that represents the indexed data. Hash B-tree indexes are also used when the index key length is longer than one-eighth of the page size for the database or 256 bytes (whichever is lower). For data values whose combined declared length is between these two bounds, Adaptive Server Anywhere uses a compressed B-tree index that stores each key in a compressed form"

Так что обобщать на все реляционные СУБД наверное не стоит...
9 ноя 06, 07:29    [3372581]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
###
Member

Откуда: Курумоч
Сообщений: 658
c127
...У хеш индексов по-моему константное время поиска...
Я бы сказал - близкое к константному. Не стоит забывать о необходимости поиска в сегментах переполнения...
9 ноя 06, 07:42    [3372590]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Зл0й
Member

Откуда: Северная Калифорния
Сообщений: 686
c127

У хеш индексов по-моему константное время поиска. В оракле 8i вроде бы были хеш индексы.


В оракле можно организовать хэш-кластер из 1 таблицы. В случае доступа по ключу этого "кластера" время грубо говоря линейное.
9 ноя 06, 07:48    [3372596]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Зл0й
Member

Откуда: Северная Калифорния
Сообщений: 686
###
[quot Зл0й][quot andsm]
B-tree - это не бинарное дерево.

Уговорили не бинарное а Б-дерево. По существу вопроса- оценке времени поиска в Б-деревьях расхождений нет? Ежу понятно что в реляционных СУБД навалом всяких разных типов индексов, речь шла про самый кондовый - сравнивали то с Кашей где данные в дереве валяюцца.
9 ноя 06, 07:54    [3372601]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
StalkerS
Gluk (Kazan)

БуГаГа, доступ по ROWID используется при переходе от индекса к записе в таблице. Будет забавно, если Oracle от этого откажется.

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


А я имел в виду, что ЕСТЬ такой способ доступа (и отказаться от него не получится). Для пользователя тоже есть и может применяться (если соображаешь что делаешь)
9 ноя 06, 09:08    [3372729]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
kvasov
к слову, а вот эти ораклы

http://www.oracle.com/technology/software/products/database/oracle10g/index.html

это прямо полнофукциоанальные, или как?
или что в них демо?


Гы, ну доступ по ROWID-у в них есть палюбому. Вас ЧТО из функциональности КОНКРЕТНО интэрэсуе ?
9 ноя 06, 09:10    [3372736]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
Зл0й
Двоичные деревья бывают разные, в различных учебниках по computer science терминология может слекга отличаться. В Oracle и реляционных СУБД используются сбаланисированные по высоте двоичные деревья. В них время поиска-вставки-удаления элемента O(log(n)). Время "обхода по порядку" дерева - O(n).


К слову, B-дерево вполне может быть двоичным. Например Вирт рассматривает 2-3 дерево как разновидность балансировки двоичного.
9 ноя 06, 09:16    [3372766]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
c127
У хеш индексов по-моему константное время поиска. В оракле 8i вроде бы были хеш индексы.


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

Даром ничего не дается, константное время поиска в хэш таблицах выливается в:

1. Поиск только по точному соответствию
2. Отсутствие возможности удаления данных
3. Необходимость разрешения коллизий
4. Вырождение таблицы при ее заполнении

Я совсем не знаю Мумпс, но мне очень сомнительно, что ее разработчики придумали какие-то принципиально новые структуры поиска (в них и B-деревья вроде появились не сразу), они оперируют все теми же структурами, которые описал Кнут (возможно с незначительными вариациями).
Поэтому заявления типа: поиск осуществляется за один шаг
у меня вызывают легкое недоумение и законное сомнение в компетентности сие ляпнувшего
9 ноя 06, 09:27    [3372819]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
Gluk (Kazan)
Я совсем не знаю Мумпс, но мне очень сомнительно, что ее разработчики придумали какие-то принципиально новые структуры поиска (в них и B-деревья вроде появились не сразу), они оперируют все теми же структурами, которые описал Кнут (возможно с незначительными вариациями).

Здорово, конечно, звучит. С одной стороны - "я совсем не знаю Мумпс", но с другой - "B-деревья вроде появились не сразу". Видимо разработчики ждали пока в Oracle сделают IOT. Можно увидеть ссылку на источник информации?

Gluk (Kazan)

Поэтому заявления типа: поиск осуществляется за один шаг
у меня вызывают легкое недоумение и законное сомнение в компетентности сие ляпнувшего

А ведь "ляпнувший" несколько раз повторил "логический шаг". Я тоже повторю - "ЛОГИЧЕСКИЙ".
Ну как обращение по ROWID. Так проще?
9 ноя 06, 09:41    [3372891]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

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

Здорово, конечно, звучит. С одной стороны - "я совсем не знаю Мумпс", но с другой - "B-деревья вроде появились не сразу". Видимо разработчики ждали пока в Oracle сделают IOT. Можно увидеть ссылку на источник информации?


В одном из обсуждений этой ветви форума. Искать ломает, ты уж извини.
Если у тебя есть информация о том, что B-деревья использовались в первых версиях M (не путать с Cache) с удовольствием ознакомлюсь, трук.
И еще, умерь свой тон, ты ВПОЛНЕ можешь оказаться НЕ ПРАВ, а здесь достаточно тех, кто сможет тебя поправить.
9 ноя 06, 10:09    [3373062]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
kvasov
Member [заблокирован]

Откуда:
Сообщений: 853
> 0< i <= log_k(N)


по правде говоря несколько удивляет, как многие легко рассуждают о Кеше, что там данные якобы тоже в неких "b-tree", также как у "прочих субд".

если не секрет, а почему сторонники этого мнения уверены в этом?
они прямо изучили исходники GT.M и их экстраполировали на Кеш?


к примеру диск - блочное устройство - в нем 10000 блоков.
если нужно считать 7140-ой блок данных, то что, винчестер вот так вот прыгает по логарифмической формуле, написанной Кнутом, ища нужный блок?
представляется, что нет - винчестер просто знает, где лежит этот блок.

почему в Кеше, при обращении set var=^Ug("Audi","Черные","5")
участники обсуждения решили что Кеш ищет данные вычисляя 20 раз логарифм?
Может Кеш просто знает, куда он записал эти данные?

Мы же не говорим Кешу - найди то, чего мы сами не знаем.
Мы ему говорим точную "координату" данных.
А Кеш просто знает, где лежат эти данные.

Ну я бы хотел послушать лекцию, или посмотреть мультик, как работает алгоритм MUMPS и как данные с диска отображаются в ОЗУ.

И почему в Кеше даже запрос Like '%35%' по миллиону автомобилей работает
3 секунды, а в Оракл 15 секунд.

Наверно потому, что Кеш начинает поиск с Audi, а Оракл еще 20 раз ищет саму Audi.
9 ноя 06, 10:24    [3373202]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
Sergei Obrastsov
А ведь "ляпнувший" несколько раз повторил "логический шаг". Я тоже повторю - "ЛОГИЧЕСКИЙ".
Ну как обращение по ROWID. Так проще?


Как помогут ЛОГИЧЕСКИЕ шаги в оценки производительности ? В ЛОГИЧЕСКИЙ шаг можно запихнуть ВСЕ ЧТО УГОДНО все зависит от уровня абстрагирования.
В таком случае, все ляпнутое следует оценивать исключительно как бесполезное сотрясение эфира.

Согласны ?
9 ноя 06, 10:28    [3373257]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Павел Воронцов
Member

Откуда: Новосибирск
Сообщений: 2400
Блог
kvasov
Может Кеш просто знает, куда он записал эти данные?

Мы же не говорим Кешу - найди то, чего мы сами не знаем.
Мы ему говорим точную "координату" данных.
А Кеш просто знает, где лежат эти данные.
...а унутре у ей неонка!

Ой, спасибо, повеселили, давно я так не смеялся! :)
9 ноя 06, 10:32    [3373297]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
kvasov
участники обсуждения решили что Кеш ищет данные вычисляя 20 раз логарифм?


Воинствующий ламеризм - это диагноз :)
Ты хоть понял что означали все эти логарифмы в предыдущем обсуждении ?
Ни Oracle ни Cache их никоем образом не вычисляет, им нафих эта ни нуна

kvasov

Ну я бы хотел послушать лекцию, или посмотреть мультик, как работает алгоритм MUMPS и как данные с диска отображаются в ОЗУ.


Я бы тоже посмотрел. Но почему-то сторонники M это скрывают (их неоднократно просили). А вот Oracle не делает из этого военной тайны

kvasov

И почему в Кеше даже запрос Like '%35%' по миллиону автомобилей работает
3 секунды, а в Оракл 15 секунд.


А вот в этом отдельные апологеты M девствительно СИЛЬНЫ. В оглашении ничем не подкрепленных цифирь, высосанных из безымянного пальца левой ноги
9 ноя 06, 11:04    [3373676]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
Gluk (Kazan)

В одном из обсуждений этой ветви форума. Искать ломает, ты уж извини.
Если у тебя есть информация о том, что B-деревья использовались в первых версиях M (не путать с Cache) с удовольствием ознакомлюсь, трук.

http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=PubMed&list_uids=513890&dopt=Abstract

Здесь, кстати, говорится, что я не прав, увы. Что ж, прошу прощения.

Gluk (Kazan)

И еще, умерь свой тон, ты ВПОЛНЕ можешь оказаться НЕ ПРАВ, а здесь достаточно тех, кто сможет тебя поправить.

А вот этого не надо. За свою неправоту я как-нибудь и сам отвечу.
9 ноя 06, 11:23    [3373918]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
kvasov
Member [заблокирован]

Откуда:
Сообщений: 853
Gluk (Kazan)

Я бы тоже посмотрел. Но почему-то сторонники M это скрывают (их неоднократно просили).


Если нам не показали мультик, это не значит, что что-то скрывается.

пожалуйста, изучай, если есть желание:

http://prdownloads.sourceforge.net/sanchez-gtm/gtm_V51000_linux_i386_pro.tar.gz?download

(правда здесь 30% на асемблере, и к Linux прилепилось мусора - 30% для компьютера VAX, но наверно ларжест-специалисты это смогут пропускать)

но 100 пудов - фишку тут понять можно, если есть желание.
9 ноя 06, 11:28    [3373968]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
kvasov
Member [заблокирован]

Откуда:
Сообщений: 853
Gluk (Kazan)

Воинствующий ламеризм - это диагноз :)
Ты хоть понял что означали все эти логарифмы в предыдущем обсуждении ?
Ни Oracle ни Cache их никоем образом не вычисляет, им нафих эта ни нуна


что совсем дурика включил?
не отличаешь поиск итерациями чужого кошелька, от точного нахождения своего?
9 ноя 06, 11:44    [3374195]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
kvasov
что совсем дурика включил?
не отличаешь поиск итерациями чужого кошелька, от точного нахождения своего?


ну мне его по крайней мере приходится включать :(
уточни, зачем Cache понадобилось ВЫЧИСЛЯТЬ какие-то логарифмы при выполнении доступа к данным ?
9 ноя 06, 12:10    [3374540]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Sergei Obrastsov
Member

Откуда: Магадан
Сообщений: 584
Gluk (Kazan)
kvasov

Ну я бы хотел послушать лекцию, или посмотреть мультик, как работает алгоритм MUMPS и как данные с диска отображаются в ОЗУ.

Я бы тоже посмотрел. Но почему-то сторонники M это скрывают (их неоднократно просили). А вот Oracle не делает из этого военной тайны

Во-первых, на этом форуме структура физического хранения данных в M уже обсуждалась (можете поискать).
Во-вторых, если уж так интересно, а искать не хочется, спрашивайте - отвечу.
9 ноя 06, 12:15    [3374592]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
pavelvp
Member

Откуда:
Сообщений: 673
Gluk (Kazan)
К слову, B-дерево вполне может быть двоичным. Например Вирт рассматривает 2-3 дерево как разновидность балансировки двоичного.
Зря ты это сказал :-) Этой фразой ты ещё больше запутаешь непонимающих (кстати, Байер предложил представление 2-3 деревьев в виде двоичных).

В-деревья основоположники класса сильноветвящихся сбалансированных деревьев (открытых всё тем же Байером). Т.е. это никак не бинарные деревья по определению. Другие структуры, другие алгоритмы.
9 ноя 06, 12:47    [3374934]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
MGR
Member

Откуда:
Сообщений: 536
Gluk (Kazan)

Ты хоть понял что означали все эти логарифмы в предыдущем обсуждении ?
Ни Oracle ни Cache их никоем образом не вычисляет, им нафих эта ни нуна


Ага, Оракл не умеет вычислять логарифм? Так и запишем!
:)
9 ноя 06, 12:52    [3375004]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
pavelvp
Зря ты это сказал :-) Этой фразой ты ещё больше запутаешь непонимающих (кстати, Байер предложил представление 2-3 деревьев в виде двоичных).


Они сами запутаются на ровном месте :) Разумеется я имел в виду, что 2-3 деревья могут быть представлены двоичными деревьями (с добавлением состояния дугам).
9 ноя 06, 13:09    [3375221]     Ответить | Цитировать Сообщить модератору
 Re: CACHE и MSSQL  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
MGR
Gluk (Kazan)

Ты хоть понял что означали все эти логарифмы в предыдущем обсуждении ?
Ни Oracle ни Cache их никоем образом не вычисляет, им нафих эта ни нуна


Ага, Оракл не умеет вычислять логарифм? Так и запишем!
:)


стебаемси ? умеет. Только при поиске в индексе эта нафих ни нуна
9 ноя 06, 13:11    [3375239]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 17 18 19 20 21 [22] 23 24 25 26 .. 106   вперед  Ctrl
Все форумы / Сравнение СУБД Ответить