Идея повторной реализации баз данных хороша для обучения, но, скорее всего, ужасно плоха для производственного кода.
Базы данных (особенно реляционные) прошли долгий путь с кучей оптимизаций, и это будет действительно очень сложнобыть где-то рядом.
При этом некоторые примечания, которые могут помочь:
- , если возможно, обрабатывать данные в памяти, записывать обратно на диск.Вы будете страдать от всех операций ввода-вывода, но, по крайней мере, вы не будете выполнять поиск по диску.Как уже упоминалось,
pandas - хорошее место для начала - 100k - это небольшое количество, с точки зрения современных БД
- эффективность чтения достигается за счет сортировки и индексации данных (btree + в современном подходе),что делает поиск
O(logN) вместо O(N).Однако проблема в том, что работать с IO на низком уровне довольно сложно, особенно если вы используете CSV, «один элемент» для вас определяется символами перевода строки, поэтому вам нужно самостоятельно выполнять поиск высокого уровня - вы не можете «вставлять» данные с точки зрения того, как большинство ОС обрабатывают ввод-вывод, потому что интерфейс последовательный.Чтобы избежать
O(N) на вставках, используйте старый трюк - напишите новые данные в конце O(N) и пометьте старый элемент как удаленный каким-либо образом.Хитрость заключается в том, чтобы иметь возможность записывать одинаковое количество байтов для маркера, то есть иметь логический флаг для каждой строки, и реализовывать «умную» логику для чтения.
Что касается уловки вставки, то здесь все простопример.Предположим, у вас есть таблица, отсортированная по id, а данные похожи на
id name amount
1 Alice 10
2 Bob 20
3 Charlie 30
И вам нужно обновить имя / сумму для id = 2.Поиск - O(logN) (если вы правильно установили .seek, что происходит с фактическим обновлением? Если вы пишете точно такое же количество байтов, вы можете перезаписать - искать в нужной позиции и записать. Т.е. изменение 20для 25 вообще нет проблем, вы пишете только то, что вам нужно (не гарантировано, но давайте пропустим низкоуровневые детали). Проблема возникает, когда вам нужно изменить, скажем, с 20 на 120.В большинстве случаев ваша абстракция хранилища представляет собой последовательный поток байтов, представьте как
id,name,amount\n1,Alice,10\n2,Bob,20\n3,Charlie,30\n # old
id,name,amount\n1,Alice,10\n2,Bob,120\n3,Charlie,30\n # new
^ everything beyond this point
needs to be re-written
Таким образом, в итоге вы получите в среднем O(N/2) (что, очевидно, ~ то же самое, что O(N))
Что вы можете сделать вместо этого: иметь «флаг», показывающий, действительна ли запись сейчас:
valid id name amount
Y 1 Alice 10
Y 2 Bob 20
Y 3 Charlie 30
Когда вам нужно выполнить обновление, пометьте старую строку как «недействительную» с помощью флагас таким же количеством байтов, что и у «правильного» флага, и в конце пишите новую строку:
valid id name amount
Y 1 Alice 10
N 2 Bob 20
Y 3 Charlie 30
Y 2 Bob 120
Операция O(logN) для поиска строки (такая же, как и раньше), O(1) для перезаписи нового флагаи O(M) для записи новых данных (поиск в конце файла не свободен), но это другая история).Недостаток - теперь вам нужно:
- реализовать оптимистический поиск с отступлением - если вы ищете данные с помощью дерева или двоичного поиска, вам нужно проверить состояние флага, и если данныеустарел - ищите конец файла и читайте его в обратном порядке
- по мере появления обновлений, неоптимизированный «хвост» растет, все больше и больше подталкивая вас к сложности
O(N) (btree может помочь, кстати).Таким образом, вам необходимо в конечном итоге сжимать данные обратно в оптимальное состояние - перечитать все данные, удалить устаревшие строки, повторно отсортировать данные и записать обратно на диск.Это то, что обычно называют «вакуум» в RDBMS.Для этого вам лучше следить за тем, «сколько строк перезаписано», а не «сколько строк в целом» - наличие этого отношения выше некоторого порога является признаком вакуума.