Базы данных своими руками.

Сейчас на форуме: UniSoft, bartolomeo (+6 невидимых)

Посл.ответ	Сообщение
Nimnul Ранг: 218.9 (наставник), 42thx Активность: 0.16↘0 Статус: Участник dotnet	Создано: 01 февраля 2011 03:12 · Поправил: Nimnul · Личное сообщение · #1 Привет, В последнее время занимаюсь разработкой своей BD+ORM не знаю кто в теме кто нет. Вкратце это отсутствие всяких тексто-подобных запросов. БД идет в более тесном контакте с кодом, за счет этого можно достичь более высокой производительности. Скажем есть класс таблицы, сами данные хранятся на винте и через мапинг файла в памяти, происходит основная работа с ним. В этот класс заранее добавляются классы индексов, например индекс последовательного доступа, или индекс сортированного доступа, или фильтрованного, или композитного. Фишка в том, что эти индексы строятся не в момент запроса, а походу поступления новых данных. Что позволяет иметь мгновенную сортировку\поиск\фильтр в любой момент времени. Посоветуйте как лучше организовать хранение one-to-many данных в файле. Скажем под неким int32 ключом был список, других int32 значений. При этом нужно учитывать что список этот может расширятся. Ключи могут удаляться, вставляться, добавляться и т.д. У меня есть кое какие мысли на этот счет, но вобщем интересны любые мнения. И второе алгоритм хранения деревьев в плоском виде, что бы можно было максимально быстро делать вставки, удаление, ну и конечно получение значения по ключу. Хотя можно и не в плоском виде, или скорее в псевдо-плоском с указателями(позициями), ведь файл это тоже самое что одномерный массив. ----- have a nice day

Soronorus Ранг: 1.0 (гость), 1thx Активность: 0=0 Статус: Участник	Создано: 01 февраля 2011 10:13 · Поправил: Soronorus · Личное сообщение · #2 а на чём вояешь ?? просто участвовал в одном проекте мы под зендом_db свояли. скажи каким способом ты отображаешь постоянные объекты: активная запись или шлюз данных? по конструкции данных один ко многим: ты хочешь своять свою структуру?, было решение основанное на матрице инцидентности Каждая строка соответствует определённой вершине, а столбцы соответствуют связям графа. на с++ была либа Boost Graph в общих чертах это: В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается: 1 в случае, если связь j «выходит» из вершины i, −1, если связь «входит» в вершину, 0 во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине) если нужен примерчик Пример выполнения алгоритма топологической сортировки Code: #include <iostream> #include <list> #include <algorithm> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/topological_sort.hpp> #include <iterator> #include <utility> int main(int , char* []) { using namespace boost; // тип графа typedef adjacency_list<vecS, vecS, directedS, property<vertex_color_t, default_color_type> > Graph; // описатель вершин typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; // контейнер для цепочки вершин typedef std::vector<Vertex> container; // тип представления дуг графа typedef std::pair<std::size_t,std::size_t> Pair; // Дуги графа Pair edges[6] = { Pair(0,1), Pair(2,4), Pair(2,5), Pair(0,3), Pair(1,4), Pair(4,3) }; // Граф Graph G(edges, edges + 6, 6); // словарь для получения номеров вершин по описателям вершин boost::property_map<Graph, vertex_index_t>::type id = get(vertex_index, G); // контейнер для хранения отсортированных вершин container c; // выполнения алгоритма topological_sort(G, std::back_inserter(c)); // Вывод результата: перебор описателей графа в контейнере, // получение порядковых номеров вершин std::cout << "Топологическая проверка: "; for (container::reverse_iterator ii = c.rbegin(); ii != c.rend(); ++ii) std::cout << id[*ii] << " "; std::cout << std::endl; return 0; если я тебя не правильно понял сорри \| Сообщение посчитали полезным: Nimnul
Promix_17 Ранг: 37.1 (посетитель), 11thx Активность: 0.03↘0 Статус: Участник	Создано: 01 февраля 2011 13:12 · Поправил: Promix_17 · Личное сообщение · #3 Nimnul пишет: И второе алгоритм хранения деревьев в плоском виде, что бы можно было максимально быстро делать вставки, удаление, ну и конечно получение значения по ключу. Хотя можно и не в плоском виде, или скорее в псевдо-плоском с указателями(позициями), ведь файл это тоже самое что одномерный массив. Используй пирамидальную структуру данных - массив, который можно рассматривать как почти полное бинарное дерево. в корне дерева - первый элемент массива. Если узлу соответствует индекс i, то индекс его родительского узла (int) i/2,левого дочернего - 2i, правого дочернего - 2i+1. \| Сообщение посчитали полезным: Nimnul
Nimnul Ранг: 218.9 (наставник), 42thx Активность: 0.16↘0 Статус: Участник dotnet	Создано: 02 февраля 2011 01:28 · Поправил: Nimnul · Личное сообщение · #4 Soronorus пишет: а на чём вояешь ?? C# Soronorus пишет: скажи каким способом ты отображаешь постоянные объекты: Если коротко то коллекцией, можно даже сказать массивом . Данные хранятся в файле который устроен страничным образом. У каждой страницы есть уникальный номер, оффсет на самом деле. Доступ к данным осуществляется через эти самые индексы о которых я говорил(последовательный, сортированный и т.д.). Индекс оперирует с номерами страниц. one-to-one, index-to-page или мап page-to-index. Так же предусмотрен кэш. Что бы не лазить на винт лишний раз. Soronorus пишет: было решение основанное на матрице инцидентности Каждая строка соответствует определённой вершине, а столбцы соответствуют связям графа. на с++ была либа Boost Graph Если я правильно понял, это разновидность BST деревьев? Не сбалансированные деревья и графы жрут много памяти. Soronorus пишет: по конструкции данных один ко многим: ты хочешь своять свою структуру?, Да свою структуру, поскольку каждый элемент подмножества должен возвращаться по номеру за разумное время . Короче я думаю что структура будет массив массивов, и возможно нефиг тут больше выдумывать. Единственное останется как максимально оптимально его хранить в плоском виде. Или я еще думал каждое подмножество хранить в отдельном файле. Promix_17 Так и поступлю. ----- have a nice day

Для печати