поиск "дыр" в ID

← →
cp.Silver © (2006-09-15 21:24) [0]

Привет, мастера!
Чтобы не устанавливать сервер на машине пользователя и не использовать BDE, программа использует сл. механизм для доступа к БД dbase: ADO -> ODBC -> dbase.
Предполагаемый размер таблиц в БД: 30000-40000 записей. При этом будут постоянно выполняться операции DELETE/INSERT. Вся работа происходит на SQL-запросах без исп. TADOTable.
Как можно догадаться в поле ID таблиц будет очень много "дыр".

Вопрос следующий: какой существует самый надежный и быстрый способ найти "дыру" и вставить запись именно туда?

Метод перебора или даже бинарный поиск будут работать очень медленно. Чтобы не использовать поиск была идея при удалении записи помещать ее ID в отдельную таблицу и потом при вставке новой записи брать ID из этой таблицы. Но этот метод еализовать пока не получается.
Какие будут предложения, примеры (если есть)?

← →
Shaman_ © (2006-09-15 22:05) [1]

Предложение не тормозить...
Извини за грубость

← →
SergP © (2006-09-15 23:02) [2]

Например в упрощенном варианте можно типа так...:

select id+1 from table where id+1 not in (select id from table)

По идее такой запрос должен выдать список дыр (но не всех). но если "заделать" эти дыры и повторить запрос, то он выдаст новые дыры.

← →
cp.Silver © (2006-09-15 23:31) [3]

2 Shaman_
Тип ответа называется "лишь бы что-то написать"

2 SergP
Спасибо, вариант неплохой. Но у меня существуют опасения, что при огромном кол-ве записей dbase может повиснуть...

← →
SergP © (2006-09-15 23:58) [4]

> [3] cp.Silver © (15.09.06 23:31)
> 2 SergP
> Спасибо, вариант неплохой. Но у меня существуют опасения,
> что при огромном кол-ве записей dbase может повиснуть...

Ну я написал для примера... Но я аналогичным способом пользовался для нахождении "дыр" в оракловских таблицах. Ничего, оракл не повис. Ну запрос конечно выполнялся несколько секунд... Но у меня записей тоже было несколько десятков тысяч. Кроме того поле было текстовым (на преобразование к числовому тоже получается время тратилось), и индекса не было по этому полю.
Думаю если имеется индекс и поле числовое, то не должно особо тормозить либо виснуть.

← →
Desdechado © (2006-09-16 12:27) [5]

Какой смысл в поиске дыр?

← →
Shaman_ © (2006-09-16 12:44) [6]

>2 Shaman_
>Тип ответа называется "лишь бы что-то написать"

Сам проанализируй что написал:
>Метод перебора или даже бинарный поиск будут работать очень медленно.
:
1. Это что это у тебя за теория насчет бинарного поска такая? С чего бы это такие дыры оказывали влияние на бинарный поиск? Для бинарного поиска вообще всеравно нарушена последовательность или нет, для него единственное условие это отсортированная последовательность чисел- и не имеет значения есть в ней разрывы или нет
2. Подскажи темному проггаммеру как ты в SQL запросах умудряешься использовать метод перебора? Или может выбираешь все подряд на клиента и там перебором ищешь нужную запись? =) Хочу тебя ратроить- в этом случае "дыры" тоже не имеют значения, если ты конечно не поставишь перед собой задачу написать код, скорость которого зависила бы от наличия дыр в индексе. Теоретический такой код можно написать =)
3. Индекс на то и нужен чтобы обеспечить абсолютную уникальность записи, и мудреж с ним ничем хорошим не обернется

Рекомендую не заниматься очень странными эксперементами а почитать литературу по основам БД

← →
cp.Silver © (2006-09-16 13:56) [7]

2 Shaman_

Да, я действительно ТОРМОЗ, да еще какой!!!
Я совершенно забыл, что в SQL-запросе поддерживается арифметика (вроде select id+1...). И раньше я действительно думал сначала выбрать все записи, а потом используя ADOQuery.FieldValues[] искать дыры бинарным поиском... Согласен на все 100% - ТУПО...

2 SergP

Несколько секунд не сравнимо со временем перебора, согласись :) А твой запрос я проанализировал и его надо только немного приспособить под мои нужды. Все ОК, спасибо еще раз :)

← →
SergP © (2006-09-16 14:41) [8]

> [5] Desdechado © (16.09.06 12:27)
> Какой смысл в поиске дыр?

Вы не поверите, но он бывает.... причем не единственный...

← →
Desdechado © (2006-09-16 15:30) [9]

SergP © (16.09.06 14:41) [8]
Верю, но не вижу смысла. Примерчик бы...

← →
cp.Silver © (2006-09-16 16:11) [10]

> Desdechado © (16.09.06 15:30) [9]
>
> SergP © (16.09.06 14:41) [8]
> Верю, но не вижу смысла. Примерчик бы...
>

Вот даже два примера:
1. Если в таблице постоянно происходит удаление/вставка новых записей (скажем около 3000 операций за сеанс работы), то если каждый раз вставлять запись в конец таблицы существует реальная угроза, что рано или поздно следующая операция вызовет переполнение максимального значения ID.
2. Во многих случаях проектирование приложений для работы с БД без учета "дыр" считается плохим тоном, но это зависит от задач, стоящих перед системой.

← →
Shaman_ © (2006-09-16 16:48) [11]

> рано или поздно следующая операция вызовет переполнение максимального значения ID
Если я ничего не путаю, FoxPro позволяет создавать автоинкремент по integer полям. Максимальное значение 2147483647. На операциях с удалением/добавлением 3000 записей за сессию имеем запас разрядности ключа на 715827 сессий. 1 сессия в день, хватит на 1961 год непрерывной работы. Если же нагрузка будет выше, то стоит вообще подумать о переходе на другую СУБД. Многие СУБД позволяют строить автоинкрементный индекс по полям большей разрядности, тогда уж точно хватит на пару миллиардов лет

← →
C@N © (2006-09-16 17:37) [12]

to [11]
а прикинь размерчик этой базы???)))

← →
Desdechado © (2006-09-16 18:31) [13]

> удаление/вставка новых записей (скажем около 3000 операций за сеанс работы)
если еще учесть, что операций вставки наверно столько же, сколько и удалений, то за чеанс только 1.5 тыс новых записей.

> 2. Во многих случаях проектирование приложений для работы с БД без учета "дыр" считается плохим тоном
Я считаю (и я не одинок), что проектирование приложений, работающих с дырами, - это плохой тон. Потому как приложению должно быть все равно, какими механизмами обеспечивается ID и есть ли в нем дыры.

← →
Johnmen © (2006-09-16 22:16) [14]

Ещё раз прошу любителей затыкать дыры обосновать своё желание. Без детского сада...

← →
cp.Silver © (2006-09-16 23:38) [15]

Desdechado
> Потому как приложению должно быть все равно, какими механизмами
> обеспечивается ID и есть ли в нем дыры.

Так в том то и дело, что используется старая версия dbase, у которой в принципе нет механизмов вроде автоинкремента для автоматизации и контроля работы с ID. Поэтому и вопрос возник.

← →
Anatoly Podgoretsky © (2006-09-16 23:48) [16]

dbase поддерживает до 10^20 знаков, итого если делать по 3000 операций в секунду, то потребуется 1 056 993 066 лет до переполнения.

← →
Desdechado © (2006-09-17 12:42) [17]

> нет механизмов вроде автоинкремента для автоматизации и контроля работы с ID
Автоинкремента действительно нет, но это не повод искать дыры. Если бы автоинкремент был, ты бы ведь смирился с тем, что использовать дыру нельзя.
А контроль ID простой - уникальный индекс.

← →
Anatoly Podgoretsky © (2006-09-17 13:00) [18]

Вообще то у dbase есть автоинкримент и уникальные индексы тоже.

← →
Desdechado © (2006-09-17 13:23) [19]

Аnatoly Podgoretsky © (17.09.06 13:00) [18]
> Вообще то у dbase есть автоинкримент
В какой старой версии он появился?

← →
Anatoly Podgoretsky © (2006-09-17 14:04) [20]

Появились в версии 7 и не только эти типы.

← →
Sergey13 © (2006-09-18 09:10) [21]

> [0] cp.Silver © (15.09.06 21:24)
> Чтобы не устанавливать сервер на машине пользователя и не
> использовать BDE, программа использует сл. механизм для
> доступа к БД dbase: ADO -> ODBC -> dbase.
> Предполагаемый размер таблиц в БД: 30000-40000 записей.
> При этом будут постоянно выполняться операции DELETE/INSERT.
> Вся работа происходит на SQL-запросах без исп.

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

← →
MsGuns © (2006-09-18 10:27) [22]

>SergP © (15.09.06 23:02) [2]
>Например в упрощенном варианте можно типа так...:
>select id+1 from table where id+1 not in (select id from table)

"Простота хуже воровства" (с)

Не надо советовать глупости. К тому же глупости вредные.

Вся ветка напоминает фразу "Когда коту делать нечего, он яйца лижет"

← →
MsGuns © (2006-09-18 10:34) [23]

Еще поражает стоеросовое упорство в преследовании галактической важности цели. Ведь десять человек уже твердят НАФИГА СДАЛИСЬ ТЕБЕ ЭТИ ДЫРЫ ? Ан нет. Все эти десятеро ничего не смыслят в космичности задумок, грандиозности цели..
А ведь дело-то скорее всего в том, что на счетчик хотят повесить несвойственные ему цели: что вроде номера чего-то там. Хотя назначение у него совершенно иное: всего-навсего однозначно и уникально идентифицировать запись в МНОЖЕСТВЕ записей, принаждежащих ОДНОЙ таблице.
Представляю себе картину:
чувак получает паспорт, смотрит в серию и номер и недоумевает почему у его старшего брата номер МЕНЬШЕ, чем у него.

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

← →
MsGuns © (2006-09-18 10:35) [24]

Пардон,
>почему у его старшего брата номер БОЛЬШЕ, чем у него.

← →
Плохиш © (2006-09-18 10:40) [25]

> C@N © (16.09.06 17:37) [12]
> to [11]
> а прикинь размерчик этой базы?

Какое отношение наличие/отсутствие "дыр" имеет к размеру базы?

← →
Barloggg (2006-09-18 15:59) [26]

действительно, дались вам эти дыры...

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

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

и все проблемы...
запускать такую процедуру раз в неделю/месяц и никаких проблем...

← →
Desdechado © (2006-09-18 16:02) [27]

> она не удаляла записи, а быстренько ставила им пометки "стерто"
типичный механизм в DBF

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

если, конечно, при упаковке не пересчитывались ключи для устранения дыр
а то бред выйдет, а не оптимизация

← →
MikhailV (2006-09-18 16:05) [28]

> Johnmen © (16.09.06 22:16) [14]
> Ещё раз прошу любителей затыкать дыры обосновать своё желание.
> Без детского сада...

Табельный номер ?

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

← →
MikhailV (2006-09-18 16:10) [30]

> Глупости. Типичное символьное поле, тем паче повторяться
> может.

Но проблема-то есть.

> MikhailV (18.09.06 16:05) [28]
> ..Табельный номер ?

См. MsGuns © (18.09.06 10:34) [23] со слов "А ведь дело-то скорее всего в том..." и далее.

← →
MikhailV (2006-09-18 16:20) [32]

> MikhailV (18.09.06 16:20) [32]
> Да я и не спорю. Просто, видимо, задача выбора
> "свободных" номеров из таблицы "занятых" извечна.

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

>MikhailV (18.09.06 16:10) [30]
>Но проблема-то есть.

"Разруха в головах" (с)

← →
MikhailV (2006-09-18 16:44) [35]

> Если мы говорим про идентификатор, то такой проблемы просто
> не существует.

Безусловно.

> Если про что-то другое, то проблемы опять-таки нет. Всё
> зависит от предметной области и алгоритма

Воистину правда, трудно не согласиться :))

← →
Barloggg (2006-09-18 16:53) [36]

а в чем проблема-то? в том что неохота весь файл перепахивать в поисках дыры?
я чего-то не понял?

а индексация спрашивается кому нужна?
вот и весь ответ.

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

это единственный вариант обеспечить идеальное быстродействие... при действительно больших объемах...

> [36] Barloggg (18.09.06 16:53)

Расскажи поподробнее про "индексирование всей базы в несколько уровней" плиз. А то упустил я что то видимо.

← →
MikhailV (2006-09-18 16:59) [38]

> индексировать всю базу в несколько уровней и вносить изменения
> сразу в несколько файлв где один - главный сама база, а
> остальные - оглавление для этой базы по каждому полю...
> на каждый файл...
Что, простите?

>Barloggg (18.09.06 16:53) [36]
>а индексация спрашивается кому нужна?
>вот и весь ответ.

Каким боком тут стояла индексация ?

Следующие 2 абзаца вообще бред какой-то. С претензиями на фиг знает какие обстоятельства ;)

← →
Barloggg (2006-09-18 17:05) [40]

о это просто поэма... можно даже сказать произведение искусства.

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

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

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

и таких оглавлений для каждого поля наделано...

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

вот такая вот история...

поиск "дыр" в ID Найти похожие ветки