На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Поиск Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Внутреннее устройство баз данных
Guru Jin X
   Сообщ. #1 ,

    Законченный оптимист
    *******
    Профиль · PM
    Поощрения: 23 Dgm
    Рейтинг (т): 117
    В общем, смысл в том, что мне нужно сделать свою базу данных, не используюя стандартные движки :)
    База данных должна включать в себя неограниченное (теоретически... на самом деле 2^32 вполне хватит :D) число записей, каждая из которых может иметь несколько подзаписей (а те, в свою очередь, ещё несколько подзаписей и т.д), т.е. иметь вложенную структуру. Поддержка перекрёстных ссылок (т.е. несколько ссылок на одну запись) приветствуется, хотя необязательна. Запись - это одно или несколько полей (чаще всего как минимум два: заголовок и данные) переменной неограниченной длины, часть из которых может быть зашифрована (ну, это уже детали).
    Требования: быстрый (а ещё лучше - мгновенный) поиск (желательно по любому полю), чтение, изменение, добавление и удаление записи вне зависимости от размера самой базы данных с минимальным "мусором" (имеются в виду различные вспомогательные данные, индексирование и т.д). Быстрая сортировка по какому-либо полю из БД тоже приветствуется, хотя для этих целей её можно и пересоздать :)
    Так вот, я бы хотел узнать, как устроены современные базы данных (внутри) или услышать какие-нибудь интересные идеи по этому поводу. Организовать быстрый поиск и чтение - это задача не сложная, а вот когда добавляется редактирование, то тут возникают проблемы. Представьте себе: база данных на несколько мегабайт, при этом нужно отредактировать самую первую запись и без тормозов.
    - Заранее спасибо!
    Wizard Bas
    Сообщ. #2 ,

      Wizard
      *********
      Профиль · PM
      Поощрения: 9 Dgm
      Рейтинг (т): 352
      Цитата
      Jin X, 8.08.04, 16:34
      а вот когда добавляется редактирование, то тут возникают проблемы.

      Без проблем ведь структура известна (и постоянна). Тоесть есть N полей с размером К байт что бы перейти к записи О нада передвинуться на (N-O)*K байт, или от начала О*К.

      Цитата
      Jin X, 8.08.04, 16:34
      Быстрая сортировка по какому-либо полю из БД тоже приветствуется, хотя для этих целей её можно и пересоздать

      Без сортировки современные БД и не работают.

      Jin X- задада не из легких. Inter Base - открытая архитектура и инфы много. DBF- тебе наверное не подойдет.
      kl
      Сообщ. #3 ,

        Profi
        *****
        Профиль · PM
        Рейтинг (т): 78
        Я бы посоветовал начать с Дейта. Там отлично описаны все принципы...
        tserega
        Сообщ. #4 ,

          Profi
          *****
          Профиль · PM
          Поощрения: 1 Dgm
          Рейтинг (т): 80
          В базах данных все основано на хешировании. Индексные файлы - как раз и есть список, в котором по ключу находится запись.
          kl
          Сообщ. #5 ,

            Profi
            *****
            Профиль · PM
            Рейтинг (т): 78
            Цитата tserega,9.08.04, 04:57
            В базах данных все основано на хешировании. Индексные файлы - как раз и есть список, в котором по ключу находится запись.

            Индексирование есть всегда, а физическая реализация может быть очень разным. Взять хотя наиболее популярные на сегодня индексы - В+ деревья и кластерные хеш-индексы... Последние кстати есть гарантия (с некоторой долей приближения в зависимости от СУБД) упорядоченности физического размещения данных. В+ - деревья не отличаются ничем подобным.
            Так что все же стоит почитать основы.
            ms
            Сообщ. #6 ,
              Member
              **
              Профиль · PM
              Рейтинг (т): 7
              Товарища Кнута почитать надо бы
              и с деревьями ознакомиться

              В общем случае разработать темплейный класс..
              Сообщение отредактировано: ms -
              Guru Jin X
              Сообщ. #7 ,

                Законченный оптимист
                *******
                Профиль · PM
                Поощрения: 23 Dgm
                Рейтинг (т): 117
                Цитата
                Bas, 9.08.04, 11:40
                Без проблем ведь структура известна (и постоянна). Тоесть есть N полей с размером К байт что бы перейти к записи О нада передвинуться на (N-O)*K байт, или от начала О*К.
                Проблема в том, что K неизвестно и может меняться. Даже если K - это указатель, то как хранить сами строки, чтобы их было легко редактировать? Т.е, упрощённо говоря, представь себе, что нужно сделать что-то типа текстового редактора, где каждая строка может быть любой длины, но к каждой должен быть мгновенный доступ, зная первые буквы. Причём, этот редактор вовсе не обязан держать весь файл в памяти.

                Вообще говоря, я не хочу использовать готовые БД потому, что прога не очень большая, а тащить в дистрибутив ещё мега 3-4 из-за движка типа BDE не хочется. Ведь даже Access стоит не у каждого. Если это действительно сложная задача, то видимо, придётся держать весь файл в памяти, но тогда есть опасность того, что данные потеряются, например, при зависании компа. А периодически записывать весь файл - это лишнее время. К тому же, только пустая БД, например, Access'а занимает больше 50kb :)
                kl
                Сообщ. #8 ,

                  Profi
                  *****
                  Профиль · PM
                  Рейтинг (т): 78
                  Для таких вещей уже давно придуманы embedded databases. Неужели 3-4 мега стоят 2-3 месяцев работы по изобретанию велосипеда?
                  Guru Jin X
                  Сообщ. #9 ,

                    Законченный оптимист
                    *******
                    Профиль · PM
                    Поощрения: 23 Dgm
                    Рейтинг (т): 117
                    Мне не нужна громадная система, которую нужно строить 2-3 месяца. Вполне пойдёт что-нибудь попроще, что можно сделать за пару дней. К тому же, эти 3 мега придётся пихать во все проги, которые используют БД.
                    Wizard Bas
                    Сообщ. #10 ,

                      Wizard
                      *********
                      Профиль · PM
                      Поощрения: 9 Dgm
                      Рейтинг (т): 352
                      БД с записями переменной длины, ?
                      Guru Jin X
                      Сообщ. #11 ,

                        Законченный оптимист
                        *******
                        Профиль · PM
                        Поощрения: 23 Dgm
                        Рейтинг (т): 117
                        Ты намекаешь на XML? :)
                        Wizard Bas
                        Сообщ. #12 ,

                          Wizard
                          *********
                          Профиль · PM
                          Поощрения: 9 Dgm
                          Рейтинг (т): 352
                          Не подходит?
                          Guru Jin X
                          Сообщ. #13 ,

                            Законченный оптимист
                            *******
                            Профиль · PM
                            Поощрения: 23 Dgm
                            Рейтинг (т): 117
                            Да я пока как-то и не разбирался с ним.
                            Если работает быстро и туда можно запихнуть любые символы (т.е. и табы, и пробелы в начале/конце строк, и "управляющие" и т.д), то может и подойти :)
                            Спасибо ;)

                            Добавлено в :
                            В Delphi даже стандартные компоненты есть для XML :)
                            kl
                            Сообщ. #14 ,

                              Profi
                              *****
                              Профиль · PM
                              Рейтинг (т): 78
                              Запихнуть можно любые. (см. например конструкцию CDATA а также Entities).
                              То что компоненты есть - это конечно круто (еще нехватало чтобы их не было), только как быть с требованием что файл на несколько мегов а тебе надо быстро искать и редактировать?
                              Я вот например столкнулся что реализация XPath (язык запросов к хмл) Engine может быть весьма неэффективной..
                              Guru Jin X
                              Сообщ. #15 ,

                                Законченный оптимист
                                *******
                                Профиль · PM
                                Поощрения: 23 Dgm
                                Рейтинг (т): 117
                                Эх! Если XML работает так же быстро, как чтение и перезапись всего файла, тогда он мне нафиг не нужен.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (2) [1] 2  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0352 ]   [ 15 queries used ]   [ Generated: 2.05.24, 18:48 GMT ]  
                                Powered by Invision Power Board(U) v1.2 © 2003  IPS, Inc.