Лектор

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

• Базы данных с 92-го года (Oracle / MSSQL / DBase)
• Java с 2000-го, немного знаю другие языки
• Яндекс СПб с 2007-го
• приложил руку к проектам:
  Маркет / Книги / Авто / Адреса ...

Цель курса

Расписание

• 12 занятий
• занятия в физ-мат лицее 239 по понедельникам
• с 18:30 до 20:00 лекция, потом до 21.00 ответы на вопросы

Формат

Лекция - рассказ, слайды, ссылки для самостоятельной работы.

Домашнее задание - практическое примение знаний, код ревью от лектора.

Зачет

• основа зачета - написанная вами работающая база данных + текстовое описание что и почему в ней сделано
• язык реализации - понятный лектору: Java/Scala/Python/Ruby
• курсовик можно писать в одиночестве, лучше группой до 3-х человек включительно

Требования к выпускникам

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

Понимание, что принципы, лежащие в основе базы данных, важнее деталей конкретной реализации.

Синтаксис гуглится в документации мгновенно, понимание приходит с опытом в ходе долгих раздумий.

База данных

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

... плюс алгоритмы и программы, для работы с этой коллекцией.

Базы вокруг нас

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

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

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

Браузер:

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

Обобщение

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

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

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

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

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

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

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

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

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

Это есть база данных...

Разберем внимательно как она устроена и какие алгоритмы используются в ней.

Обычная записная книжка ... Мэрилин Монро

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

• носителем информации является бумага
• информация вносится ручкой
• удалить информацию невозможно - можно только зачеркнуть
• на одной странице книги может быть от 0 до N записей
• каждая страница книги имеет свою букву (или пару букв)
• для букв Й и Ы и ряда других страницы нет (А почему?)

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

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

может содержать

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

состав информации определяется хозяином книги

Алгоритм: Добавление записи

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

• находим нашу записную книжку
• находим страницу на букву С (самбо)
• ищем свободное место
• делаем запись
• закрываем книгу
• бросаем где лежала

Алгоритм: Поиск

подтекает кран, нужен телефон сантехника

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

Алгоритм: Обновление

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

• находим нашу записную книжку
• открываем страницу на букву К (Коля)
• ищем запись "дядя Коля"
• зачеркиваем запись
• ищем свободное место
• делаем запись
• закрываем книгу
• бросаем где лежала

Алгоритм: Удаление

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

• находим нашу записную книжку
• открываем страницу на букву Ш (школа)
• ищем запись про завуча
• зачеркиваем (тщательно, два раза)
• закрываем книгу
• бросаем где лежала

Итого алгоритмы / операции:

Общее в алгоритмах (всегда)

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

Почти всегда мы сразу позиционируемся на какую-то страницу - факты, содержащиеся в информации позволяют "оптимизировать" процесс поиска

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

Задача: позвонить всем одноклассникам

Нам ни чем не поможет разделение на страницы...

Придется перебрать все страницы...

... и все записи на всех страницах.

Но шаги "найди базу, закрой базу" все равно будут с нами.

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

Информация:

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

Чуть чуть ключевых понятий

• кто такой инженер
• что такое o(n)
• что такое "компьютер - ну очень быстро ..."

Ошибки инженеров

Что такое o(n)

wikipedia:«O» большое и «o» малое wikipedia:Big_O_notation

Пусть наш компьютер делает 1000 операций в секунду...

Примеры o(n)

• o(n) - последовательный перебор (full scan)
• o(n^2) - сравнение всех со всеми
• o(ln(n)) - бинарный поиск
• o(n ln (n)) - сортировка quick sort
• o(k * n) - wikipedia: radix sort

Скорость поиска в телефонной книге структуре

• ищем нужную страницу
  - линия от А до Я с О(c * n=28)
  - бинарный поиск в отсортированном A-Я O(ln(28))
• открываем (загружаем) нужную страницу с O(c * 1)
• линейно, начиная сверху, перебираем записи, пока не найдем нужную - O(c * n малое [~ N/28])

Если хранить без деления на страницы, т.е. простым списком

• скорость поиска - O(N)

Ограничения физического мира

• скорость random memory access
• скорость sequencial memory access
• скорость random disk drive access
• скорость sequencial disk drive access

Вопрос:

• Ищем 1000 записей - 100Мб последовательно или 1000 random access?
• Сеть - диск - память - ЦПУ кэш - где использовать random vs sequencial?

Блог Романа Елизарова: Память: последовательный доступ vs случайный доступ. Как замерить?

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

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

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

• бумага (носитель)
• скорость человека (вычислительная мощность)

Итого

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

• хорошая (люди пользуются)
• эффективная (o(n) etc)
• понятная (и пользователю ... и инженеру)
• надежная (годами работают)
• проверенная временем (столетия, наверное)

... настоящая база данных

Заметки для инженера

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

Быстрая имплементация может понятной.

Сохраненные данные статичны и добавление новой информации экономно.

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

Вопросы?

• web: Илья Тетерин
• twitter: @ya_pulser
• email: ya.pulser at gmail.com
• слайды: http://fluffypulser.ru/static/dbcourse.2012/index.html

Домашнее задание, часть #1

Своя база данных на Java (Ruby/Python/etc)

• телефонная книга - фио + телефон - на arrayList
• CRUD операции, в формате add (ivanov, Иванов, +7921AAABBCC) / get (ivanov)
• доступ к через какой-либо api ( console / http / socket - на выбор )
• возможность сохранить в файл, дабы можно было перезапустить сервер ( flush / commit / snapshot )