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

10

Общий вопрос

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

Некоторый контекст

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

В настоящее время я работаю над улучшением моего понимания алгоритмов, которые, конечно, в значительной степени задействуют структуры данных. Это основные структуры, такие как Bag, Queue, Stack, Priority Queue и Heap.

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

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

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

Итак, вот вопросы ...

Вопросов

  1. Каковы различия между структурами данных и базами данных?
  2. Когда мы используем алгоритмы, которые используют структуры данных, определенные исключительно в вашей собственной логике, а не в логике базы данных?
  3. @Harvey post: Когда методы в базе данных становятся менее эффективными в использовании, чем методы в вашей собственной логике?
    • @mirculixx post: Что делает метод эффективным?
  4. @ Харви пост: Как быстрее обрабатывать данные со структурами данных, чем делать это в базе данных?

Разъяснения

  1. @Grant post: базы данных, с которыми я обычно работаю, реляционные, и эти вопросы возникают из-за работы с ними. Тем не менее, я думаю, что эти вопросы применимы к любой персистентной структуре (когда я говорю «структура», я имею в виду это в самом общем смысле).

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

Халкмейстер
источник
Datomic.com база находится ближе к пользователю , чем традиционные реляционные. Вы смотрите только на традиционные базы данных?
Работа
@ Job Нет, реляционные базы данных - не единственное, что я рассматриваю здесь. Это больше о понимании различия между структурами данных в логике и структурами данных в базе данных / персистентности.
Халкмейстер
Как правило, я бы сказал - используйте базу данных, если можете, но если она становится слишком медленной, прибегайте к использованию структур данных. Дублирование данных (например, кеширование) плохо, потому что вы должны синхронизировать их, поэтому избегайте, если не можете.
Работа
Отправить данные в базу данных только для сортировки? Как ездить по кварталу, чтобы передумать?

Ответы:

18

Структуры данных, по большей части:

  1. Резидент памяти,
  2. Переходная,
  3. Ограничен в размерах,
  4. Не возвращаться без добавления механизмов параллелизма, таких как блокировки или неизменность,
  5. Не соответствует кислоте ,
  6. Быстро, если выбран тщательно.

Базы данных по большей части:

  1. Диск переплет,
  2. Стойкие,
  3. Большой,
  4. Безопасно одновременно,
  5. Совместимый с ACID, с транзакционными возможностями,
  6. Медленнее, чем структуры данных

Структуры данных предназначены для передачи из одного места в другое и используются внутри программы. Когда вы в последний раз отправляли данные с веб-страницы на веб-сервер, используя базу данных, или выполняли вычисления для базы данных, которая полностью находилась в памяти?

Системы баз данных используют структуры данных как часть их внутренней реализации. Это вопрос размера и объема; Вы используете структуры данных в своей программе, но система баз данных - это отдельная программа.

Роберт Харви
источник
Что касается замечания веб-сервера к веб-сайту, я согласен, что вы не будете использовать базу данных там, но я вижу возможность существования сервлета для обработки или перевода этих данных для сохранения в базе данных. Между средним уровнем и уровнем данных все становится немного запутанным. Чтобы упростить вопрос, когда методы в базе данных становятся менее выгодными для использования, чем методы в логике?
Халкмейстер
1
Ну, это хлеб с маслом DAL, не так ли? DAL существуют для облегчения перехода между объектами и записями базы данных. DAL подходят примерно на 80–90 процентов от того, что вы хотели бы сделать с базой данных, но для оставшихся 10–20 процентов вы можете захотеть вернуться к необработанному SQL или хранимым процедурам, потому что это более эффективно.
Роберт Харви
В вашем примере сортировки / фильтрации вы правы в том, что вы, вероятно, хотите выполнить такую ​​обработку на сервере базы данных. Но вы, скорее всего, все равно получите результат этой обработки в виде некоторой формы структуры данных.
Роберт Харви
Точки, которые вы дали, были действительно информативными. Тем не менее, меня все еще что-то беспокоит насчет методов (или алгоритмов), которые работают с базой данных напрямую или просто со структурами данных строго в рамках логики или обоих. Я смотрю на пункт 6 обоих списков, которые вы записали, и возникает вопрос: как один быстрее другого? Я всегда считал, что работа с данными в источнике - это самый быстрый способ решения проблем. Вы можете обновить в своем посте - я перечитал его.
Халкмейстер
1
Базы данных работают медленнее по ряду причин. Несмотря на кэширование, вы должны читать данные с диска, используя SQL-оператор, который нужно скомпилировать, имея план выполнения, часто включающий несколько таблиц. Процесс намного сложнее. Кроме того, вам, как правило, все еще приходится передавать результат по сети, где вы переводите данные в структуры данных, чтобы вы могли с ними работать.
Роберт Харви
6

Каковы различия между структурами данных и базами данных?

На абстрактном уровне их нет - база данных - это структура данных.

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

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

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

В тенденции я бы поспорил

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

б) использовать свою собственную (в памяти) структуру данных, если скорость выполнения имеет значение, или постоянство не требуется

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

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

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

Ответ во многом зависит от обстоятельств и (типа) используемой базы данных. Я бы перефразировал вопрос "что делает метод эффективным?" Затем он становится упражнением в оценке методов (= алгоритма), которые вы бы использовали для своей структуры данных, по сравнению с методами, используемыми базой данных. Также см. Следующий пункт.

Как быстрее обрабатывать данные со структурами данных, чем делать это в базе данных?

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

miraculixx
источник
1

Доступ к диску - это в первую очередь то, что является наиболее дорогим в этой операции, чаще, чем доступ к сети (http://serverfault.com/questions/238417/are-networks-now-faster-than-disks). Если ваша база данных не находится по крайней мере в сети 1 Гбит / с и в той же сети, что и ваш сервер веб-приложений, производительность сети не будет иметь такого же значения, как производительность диска для больших наборов данных. Или, если ваши данные находятся на очень быстрых твердотельных дисках, которые будут быстрее, чем обычный доступ к сети. Кроме того, базы данных обычно предоставляют механизм IPC, такой как именованные каналы, вместо использования TCP / IP, если база данных находится на том же сервере, что и сервер приложений.

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

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

Питер Смит
источник
Пожалуйста, скажите мне, правильно ли я понял. Применяя сказанное вами, всякий раз, когда я думаю о работе с данными, если я могу сохранить рабочий набор в кэше в памяти, это происходит быстрее. В противном случае, попробуйте использовать базу данных для получения этих результатов или найти способ привлечь больше запросов к базе данных?
Халкмейстер
@hulkmeister Да, как правило, если набор данных не очень маленький или база данных не удалена от вашего местоположения в медленной сети.
Питер Смит
0

Что вы подразумеваете под базой данных? Вы имеете в виду реляционную базу данных, такую ​​как MySQL или SQL Server? Реляционная база данных - это структура метаданных, которая поддерживает некоторое подмножество операций, определенных реляционной моделью . Теория реляционной модели, которая была разработана Эдгаром Коддом в 60-х годах.

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

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

Чарльз Э. Грант
источник
Извините, просто нужно уточнить, что означает "довольно-таки немного" по отношению к последнему абзацу?
Халкмейстер
@hulkmeister, извините, это должно было быть «большим», а не «битым». реляционная модель очень абстрактна и довольно сложна. Обеспечение реализации, которая на самом деле работает адекватно, особенно та, которая обеспечивает ACID ((атомарность, согласованность, изоляция, долговечность), требует много довольно сложного кода, работающего за кулисами.
Чарльз Грант