Привет всем.

Да, да, нужно разработать клиент-серверную реляционную СУБД. Это мой КУРСОВОЙ в универе, ничего больше) К сожалению, читать исходники postgres, berkeley и других нету времени, так что пришлось создать топик (хотя сегодня думаю порыться в исходниках sqlite и leap).
Теорией немного подковался, теперь возникли более-менее конкретные вопросы, направленные на систематизацию и увязку знаний, плюс по деталям реализации.

1) Читал в wiki про ISAM (http://ru.wikipedia.org/wiki/ISAM), смутила фраза
"Второй набор данных — индексы, содержат указатели, которые позволят извлечь определенные записи без поиска по всей базе данных. Это несколько отличается от индексов в современных поисковых базах данных, так как в них индексы хранятся прямо в записях."
Вроде как многие современные СУБД используют b-деревья для индексов и хранят их отдельно от данных. В MSSql отведены отдельные страницы для индексов, если я не ошибаюсь. Да и вообще хранить индексы вместе с данными не очень рационально, как мне кажется. Может есть какие-то новые веяния? Как лучше хранить индексы: с данными или нет?
2) В каком виде лучше всего хранить индексы в оперативной памяти? Так же как и физически - b-дерево (или его часть, если есть ограничение по выделяемой ОЗУ)? Возможно вопрос немного странный, но в описании MуSql говорится про дополнительное использование хэш-таблиц: "Хеш-таблицы в памяти, используемые как временные таблицы."
3) Во время поиска (в т.ч. не по индексам), насколько я понимаю, постоянно придётся подгружать-выгружать данные в-из оперативную память. Чтобы ускорить эти процедуры, данные на внешнем накопителе разбивают на страницы? Стоит ли заморачиваться способом чтения файлов БД: вызовы CreateFile-ReadFile-WriteFile, fopen-fread-fwrite или через проекции в оперативную память File Mappings?
4) Как лучше организовать кэширование данных: по наиболее частым запросам или по наиболее используемым записям (в совокупности от нескольких запросов)? Или дело вкуса?

Буду благодарен за ответы.

kdvпо-моему, писать свою СУБД на курсовой - это слишком опрометчивое решение.
kdvВ общем, предсказываю фиаско. Вам теорию до начала написания кода читать и читать.
Возможно так кажется со стороны.

kdvТиори и Фрай "Проектирование баз данных"
Спасибо, посмотрю. Пока что прочитанный Дейт мне не слишком много нового дал.

kdv
автор
В каком виде лучше всего хранить индексы в оперативной памяти?

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

Это понятно. Так сделано,например, в MsSql, верно? Страница - это всего лишь промежуточный абстрактный уровень хранения так сказать, А сами индексы по структуре связаны в b-дерево. Может я не совсем понятно выразился, но в данном вопросе я хотел УТОЧНИТЬ саму структуру индекса подгруженного полностью или частично в оперативную память, вернее стоит ли её дополнять и преобразовывать. Для чего же тогда в MySql используются "Хеш-таблицы в памяти, используемые как временные таблицы."?

Dimitry Sibiryakov
За leap не скажу, но sqlite вроде бы как не клиент-серверная?..

Клиент-серверность я сделать смогу)) Меня сейчас интересует именно ядро СУБД. А организовать сокет и сделать обслуживание подключённых клиентов в потоке не очень сложно.

Первое, что надо сказать, это огромное спасибо, народ, что не поленились ответить. СПАСИБО всем, кто принял участие в обсуждение.

kdv
гм. я бы сказал, что Дейт тут вообще ни при чем.

Я сказал то же самое) Научный руководитель посоветовал читать Дейта "Введение в системы баз данных", но пользы это принесло мало.

kdv
без понятия. это фишка конкретного сервера или конкретного движка MySQL. Временные таблицы у всех по разному реализуются.

Я уже разобрался для чего) В таблицах InnoDB при БД небольшого размера, которая полностью или почти полностью вмещается в оперативную память, MySQL на основе B-дерева строит хэш-таблицу, считая, что в данном случае это ускорит доступ.

mayton
Даже если ты "прочитаешь" все исходники postgres, berkeley - это не поможет тебе быстро ответить на твои вопросы. Такой способ ПОЛУЧЕНИЯ ЗНАНИЙ - неприемлим.

Да, для быстрого получения знаний это не подходит. Сейчас читаю статьи по СУБД, большинство из них правда на английском, но мне это не сильно мешает)

mayton
API не имеет значения. Все файловые API примерно одинаковы. На низком уровне это - открыть файл. Прочитать байть (или блок байтов). Закрыть файл. В качестве страницы можешь выбрать строку dbf-файла. Или блок строк. Это удобно т.к. строки dbf имеют физически одинаковый размер.

Имеет. File Mappings работают через механизм страничной организации виртуальной памяти. fread и компания осуществляют дополнительную буферизацию данных и могут без "доточки" использоваться для чтения небольших порций. ReadFile и КО - то, что в конце концов вызовет fread - лучше использовать для чтения больших объёмов и разбираться с буферизацией самому, но зато сам знаешь где и как буферизиризация происходит.

mayton
Это глубокая оптимизация. На данном этапе это не имеет абсолютно никакого значения т.к. не с чем сравнивать и нет нагрузочного теста. Сделай хотя-бы работающий макет. А там будет видно.

Да, я от кэширования отказался. Просто не успею. Лучше потом добавить, если время будет.

opendsa
1. Это однопользовательская база или много пользовательская.
2. Каким временем Вы располагаете.
3. Нужно что бы работало или просто показать и сдать.

Многопользовательская, подробнее ниже.
Времени маловато.
Чтобы работало и сдать. Не сверхсложное, но и чтобы стыдно не было.

opendsa
На этом уровне все абстракция.
Вам нужно создать прозрачный механизм быстрого поиска ( прямой и коственной адресации данных через индексы).
Диск <-> Память (индекс) + Диск <-> Память (Данные)
Обычно для этого используется абстракция под названием ROWID.
Только формулы , алгоритмы сортировок и блок схемы уже потянут на курсовую.

ROWID - это, насколько я понимаю, физический адрес записи (файл->блок->страница->номер_записи), который заодно используется как уникальный идентификатор???

opendsa
Как вы ответили на первый вопрос ?
Много пользовательская ?
Значит погружайтесь в мутексы ( синхронизацию паралельного выполнения)
и распределение ресурсов,
Тут еще одну курсовую хватит.

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

opendsa
Механизм LRU тут еще на одну курсовую насобирать можно.
Учитывая приоритетность вытеснения ( Данные , Индексы, Метаданные и т д.)

Как я уже написал, кэширование исключил из планов.

opendsa
все зависит от того, что требуется от прототипа.

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

mayton
Парень! Это всего-лишь курсовой! Автору надо просто продемонстрировать РСУБД. И ничего более. Выполнить программу-минимум. Я понимаю твоё рвение, но это, поверь не тот случай.


opendsa
Человек спрашивает - я отвечаю.

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

И на диплом и даже на дисерт хватит при должном подходе.

Да всё нормально, мне как минимум нужно было узнать "потолок" этой работы и оценить время.

Возможно завтра покажу спецификацию требований.

Ещё раз: всем спасибо.

Наверное, будет правильным, если я отпишусь о результатах)
СУБД написана, курсач сдан.

Был создан прототип колоночной СУБД. В общем-то с самого начала я на такую схему и рассчитывал - сделать что-то новое в строковых хранилищах очень тяжело. А колоночные на данный момент - непочатый край работы, куча вариантов и идей)) Ну надеюсь, мысль понятна. Хотя скажу сразу: при разработке мне показалось, что строковую было бы написать гораздо легче.

Что конретно было реализовано (Язык - C со вставками C++ :) ):
- Менеджер страниц (диск <-> память) с поддержкой многопоточности
- Полные индексы на основе B+ деревьев (без кластерных, добавление новой записи идёт точно в конец таблицы)
- Многопоточная обработка запросов: вставка и выборка (без удаления). Выборка только с критерием AND (немного упростил задачу :))
- 5 базовых типов данных: INT32, UINT32, DOUBLE, STRING (аналог char в mysql), TEXT - просто текст нефиксированной длины, максимально 32 килобайта. В общем потом добавил byte и short int. Это непринципиально как вы понимаете.
- Многопользовательский доступ по сети.

Результаты:
Тестовая таблица - INT (индекс/primary index в MySQL), INT, STRING, TEXT, DOUBLE, INT.
Время вставки 5000 записей - в 2 раза больше, чем в MySQL (0.16 и 0.08).
Время выборки 2000 записей из 5000, находящихся в таблице более чем в 10 раз меньше (0.0012 и 0.03).
Естесственно, это результаты только прототипа, а не полноценной СУБД, но при конечной реализации я думаю результаты не изменятся слишком сильно. Код СУБД - не оптимизировался специально, результаты только за счёт колоночной модели.
Тесты при многопользовательском доступе не проводились.

Замечания:
Самые сложные места в разработке - это проектирование архитектуры и синхронизация потоков (для синхронизации доступа к B+ дереву пришлось придумывать спин-блокировку с 3-мя состояниями :)).

Резюме:
Преимущества и недостатки колоночных СУБД подтверждены на практике.
Если кому-то придёт в голову взять на курсовой и диплом СУБД, вот мой совет - ну его нафиг)

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

kdvгигант...

спасибо, коль не шутите.

smansdbSoFx00 Самые сложные места в разработке - это проектирование архитектуры и синхронизация потоков (для синхронизации доступа к B+ дереву пришлось придумывать спин-блокировку с 3-мя состояниями :)) На Java синхронизация многопоточности выполняется элементарно…

Java - это не язык для написания быстрой СУБД. Я плохо знаком с явой, но вряд ли средства синхронизации в ней сильно отличаются от имеющихся на Win32 и алгоритмических: те же критические секции и проч. Тройной спинлок нужен для быстрой многопоточной работы с b+ индексами. Поясню: один поток начинает читать индекс, второй тоже хочет читать. Если тупо блокировать работу с индексом - огромное падение производительности, т.к. второй поток вынужден ждать окончания чтения, вместо выполнения параллельно. Поэтому надо вводить 3 состояния - чтение, запись, не_используется и на их основе строить логику новой спинблокировки.