Программирование своей БД. Чтения/запись БД несколькими юзерами. (Си)

Тема в разделе "WASM.PROJECTS", создана пользователем Rel, 23 янв 2009.

  1. 2FED

    2FED New Member

    Публикаций:
    0
    Регистрация:
    20 фев 2008
    Сообщения:
    1.002
    хорошая идея к стате, прийму на заметку ;) а ещё можно сделать функцию дефрагментирования базы
     
  2. _basmp_

    _basmp_ New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2005
    Сообщения:
    2.939
    2FED
    тут видимо не статья нужна. это просто пару слов на тему. хорошо бы саму либу изделать.
    дефрагментацию можно делать. можно даже индикатор фрагментированости прицепить. Только само оно не сделается.

    Rel
    связи между таблицами по полю - нормальное свойство бд.
    (http://sourceforge.net/project/showfiles.php?group_id=4451&package_id=4468)
    проблема в самой организации. быстрый доступ к записи, модифицируемость, малая избыточность, многопользовательская/многопоточная работа, защищенность от сбоев, варианты данных допустимых к помещению в запись/поле, приватность итд. подумать об этом будет интересно и полезно.

    вобщем я сказал. а как вы - говорите. авось что и выгорит
     
  3. 2FED

    2FED New Member

    Публикаций:
    0
    Регистрация:
    20 фев 2008
    Сообщения:
    1.002
    _basmp_ я имел ввиду "кстате" а не "к статье" :)

    угу мне тож идея очень нравица, просто недавно делал подобие ini файла.
     
  4. _basmp_

    _basmp_ New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2005
    Сообщения:
    2.939
    один тс, один пожелавший рук доложить, один просто небезразличный и дело встало. место под проект володя предоставляет. с траком вики и проч.

    (жуткая вещь эта вики. удивительно работящие и удивительно близорукие школьники ее разработали. даже удивительно ее популярносте. видать за неимением конкурентов)
     
  5. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.322
    прежде чем начинать разработку чего то, необходимо решить в какой среде будете реализовывать? С++? далее как база будет теоритически выглядеть? как будет происходить внутреннее связывание? как баз будет хранится в памяти во время выполнения? как база будет хранится в файле? и многие другие...

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

    _basmp_ New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2005
    Сообщения:
    2.939
    Rel
    на чем писать тут дело 10е. хоть на 3х разл языках 3и разл реализации. а вот сам формат файла(ов) бд обмозговать - самое важное.
    (лучше не писать кучей, а по пунктикам. в формате

    <номер>) <критика>; <предложение>; <обоснование>.

    и через строчечку. так будет читабельнее)

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

    пример

    Код (Text):
    1. uint32 magic;
    2.  
    3. struct Header {
    4.    struct RecordRoot* recordsList;
    5.    struct RecordRoot* recordsIndexTree;
    6.    struct RecordRoot* deletedList;
    7.    struct RecordRoot* deletedLengthTree;
    8. //---------
    9.    char* indexCriterion;
    10. //---------
    11.    char* fieldsDesc;
    12. };
    13.  
    14. struct RecordRoot {
    15.     char writeLock;
    16.     char flags[3];
    17. //--------
    18.    struct RecordRoot* left;
    19.    struct RecordRoot* right;
    20. //--------
    21.    struct RecordRoot* prev;
    22.    struct RecordRoot* next;
    23. //--------
    24.    struct Record* record;
    25. };
    26.  
    27. struct Record {
    28.   int length;
    29.   union {
    30.     struct {
    31.       int64 writeDateTime;
    32.       struct Record* variant;
    33.       char  record[1];
    34.     } live;
    35.     struct {
    36.       struct Record* left;
    37.       struct Record* right;
    38.     }deleted;
    39.   } d;
    40. };
    и место под запись выделять определенными порциями. например степенями 2ки. это облегчит расширение записи, ускорит перезаюзывание поиск/сортировку удаленных записей. и не приведет к большой избыточности (предполагаю. надо продумать/проверить)

    (чето голова уже не варит. завтра проверю/поправлю/дополню)
     
  7. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.322
    рассматривая формат файла, я предлагаю делать так:
    - у каждой записи есть набор "позиций" вида:
    -- смещение позиции относительно начала файла
    -- количество данных по позиции

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

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

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

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

    что думаете по этому поводу?
     
  8. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    дайте определение слову "позиция".
     
  9. _basmp_

    _basmp_ New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2005
    Сообщения:
    2.939
    Rel
    простой пример.

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

    и такой вопрос

    зачем вам нужен быстрый доступ по номеру несортированой записи? где это так часто применяется?
     
  10. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.322
    я наверное непонятно объяснил... вот допустим есть файл, в нем:

    <НАЧАЛО_ФАЙЛА> БАЗ00000АДАН0000ЫХ00000000000..................... <КОНЕЦ_ФАЙЛА>

    здесь показан вариант хранения строки "БАЗАДАННЫХ" в файле, нули - это какая-то другая информация (другие поля, не представляющие на данный момент интереса)... таким образом, чтобы знать, что где данная строка хранится в файле, нужно индексирование... индексирование предлагаю делать парой чисел (смещение относительно начала файла, количество данных по смещению)... то есть строка в индексе будет выглядеть, как набор: (0, 3), (8, 4), (16, 2) - то есть фактически координаты кусочков строки в файле базы данных...

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

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

    извините, не понял вопроса... и к чему он был задан...
     
  11. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    Rel
    какие форматы данных можно будет хранить в файле БД?

    интересный топик, тем более что после "ожирения" MySQL "лёгеньких" субд практически не осталось.

    P.S.
    ссылка из #12(ESDB) не открывается :dntknw:
     
  12. Voodoo

    Voodoo New Member

    Публикаций:
    0
    Регистрация:
    9 апр 2003
    Сообщения:
    297
    Адрес:
    Новосибирск
    t00x
    а sqlite не легкий?
     
  13. _basmp_

    _basmp_ New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2005
    Сообщения:
    2.939
    Rel
    -- как вы хотите получать доступ к отдельной записи еще до первой индексации?
    -- индекс у вас - линейный список?
    -- зачем нужны длины записи в индексе
    -- как вы предлагаете реализовать произвольное количество полей между разными записями одной бд? как с этой фичей вообще работать??

    предлагаю вопроса полей пока не касаться. сначала определимся с записями и навигацией по ним
     
  14. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.322
    вообще я предпологал основной упор делать на строки, но также предполагал хранить неограниченого размера целочисленные типы (знаковые и беззнаковые), а так же неограниченные числа с плавающей точкой... но об этом потом поговорим...

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

    по сути дела да... список записей вида (смещение относительно начала файла, количество данных по смещению)...

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

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

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.322
    UP! чеж все тему забросили, или кроме меня ни у кого идей нет? >:dntknw:
     
  16. _basmp_

    _basmp_ New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2005
    Сообщения:
    2.939
    тему не забросили. просто я щас немного крепко занят.

    про ваши идеи - напишу.

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

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

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

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

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

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.322
    да... с этим канеш полностью согласен...

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

    тот вариант, что вы предложили, хранит либо действующий элемент базы, либо, если элементы был удален, указатели на предыдущий и следующий элемент... но из этого следуют несколько ограничений... я предлагаю немного переработать ваш вариант в плане самой записи, что если делать так:
    Код (Text):
    1. struct Record
    2. {
    3.  bool bIsAlive;                 // false - запись удалена, true - запись активна
    4.  int writeDateTime;
    5.  rec record;                    // данные по записи
    6.  uint32 nextRecordOffset; // смещение следующей записи, относительно текущей
    7.  uint32 prevRecordOffset; // аналогично смещение предыдущей записи, если понадобится канеш
    8. }
    это позволит восстанавливать удаленные записи, а так же хранить данные произвольной длины... однако канеш доступ к элементу в конце файла будет происходить через суммирование всех смещений, в этом существенный минус... еще пока не особо понятно, как сортировать такие записи, и как их отражать в память... но это уже другой вопрос, обсудим его позже... ;)
     
  18. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    Код (Text):
    1. struct Record
    2. {
    3.  ...
    4.  int writeDateTime;
    5.  ...
    6. }
    это зачем?
     
  19. _basmp_

    _basmp_ New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2005
    Сообщения:
    2.939
    t00x
    для поддержки многопользовательской/многопоточной работы.

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

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.322
    можно канеш ограничиться флажком блокировки открытия элемента на запись... но с "числодата" канеш красивее, хоть и проблем в реализации больше....