Базы данных: введение

Илья Тетерин
2011-09-14

(use arrow keys or PgUp/PgDown to move slides)

Цель курса

Познакомить слушателей с принципами построения систем хранения данных.

Показать распространенные проблемы и варианты их решения

Дать навыки оценки готовых реализаций и работы с ними

Лектор

Илья Тетерин / ya.pulser@gmail.com

Требования

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

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

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

Расписание

Зачет

База данных

В пределах этого курса "База данных" это некий набор информации, потенциально необходимой в дальнейшем.

... плюс алгоритмы и программы, для работы с этим набором.

Вокруг нас

Рассмотрим несколько примеров баз данных вокруг нас

Сотовый телефон

  • список контактов в адресной книге
  • список совершенных звонков
  • список полученных и отправленных смс

Браузер:

  • список закладок
  • список посещенных страниц
  • набор cookies, установленных разными сайтами

Книга

  • список глав и абзацев
  • оглавление книги как способ быстрого поиска / toc
  • index (список слов в конце книги со ссылкой на страницу)

Обобщение

Любой случай, когда при описании упоминается "список чего либо".


Из чего следует, что даже "список покупок" - тоже база данных.

Список покупок:

  • перечисление в произвольном порядке имя товара и количество

Чуть более сложно

Файловая система вашего компьютера
большая БД с очень большой функциональностью (журналируемые, распределенные)
кэш (набор файлов) внутри IntelliJ IDEA
из которого на лету подсказываются имена классов и методов
Google Maps
распределенная база данных содержащая не только текст, но и точки и многомерные объекты
Компьютерная игра
описание уровня и наборы графики, для их отображения
(... как красиво внутри хранились данные в Doom ...)

Бумажная телефонная книга

У каждого человека есть бумажная записная книжка

... либо такая есть у его мамы или бабушки.

Она лежит где-то дома, извлекается на свет, когда надо позвонить дяде Коле в Воронеж или найти телефон сантехника.

В ней находится информация, которая нужна, но не прямо сейчас, а потенциально, в будущем.

Имплементация телефонной книги

"Запись" в телефонной книге


содержит обычно

  • номер телефона (с префиксом города или без)
  • имя человека

может содержать дополнительную информацию

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

Добавление

нам надо записать телефон тренера по самбо

Поиск

нам надо найти телефон сантехника

Обновление

у дяди Коли сменился адрес и телефон

Удаление

знать не знаю, не хочу знать завуча из школы

Итого мы знаем как:

  • добавить запись в книгу
  • получить запись из книги
  • обновить информацию в книге
  • удалить информацию из книги

C R U D

  • create
  • retrieve
  • update
  • delete
wikipedia:Create,_read,_update_and_delete Базовые операции с данными ...

С точки зрения инженера

Информация:

Скорость поиска в такой структуре

Сравнение с простым списком

Достоинства

В полностью отсортированным списке было бы О(ln(n))

А нас получается для 100 элементов: ln(28) + 100/28 = 3.3 + 3.6 = 7 по сравнению с ln(100) = 4.6

Что на самом деле очень неплохо, так как список букв - пресортирован и не меняется.

За счет структуры (особенности имплементации) книжки - сложность уменьшается в 15 раз, по сравнению с простой записью

O(n) vs O(ln(28)) + O(n/28)

Почему имплементация именно такова

Ограничения физического мира накладывают ограничение на доступные решения.

Сложность использования полностью оптимального решения (посортируйте от руки на бумаге).

Итого

Бумажная телефонная книга:

Для инженера

При работе с данными нас могут удовлетворить значительно упрощенные структуры.

Понятная имплементация позволяет получать данные достаточно быстро.

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


Я хочу, дабы вы смотрели на мир с такой стороны.

Вопросы?