База по Базам Данных - Storage (Индексы, Paging, LSM, B+-Tree, R-Tree) | Влад Тен Систем Дизайн

Всем привет. Добро пожаловать на первый урок по распределённым системам и системдизайну от Владатена.

Значит, перед тем, как нам дизайнить систему, состоящую из множества компонентов, да, нам нужно разобраться, что происходит в самом главном компоненте, а именно в сторедже. Значит, эту и все следующие лекции мы будем говорить про стордж и будем говорить в рамках только одной ноды. Только одной ноды. А дальше уже мы будем придумывать, как его там распределять, как его реплицировать, как его шардировать, что там ещё можно сделать. Поговорим там про алгоритмы консенсуса и про всё прочее. Но сначала давайте разберёмся, что происходит с одной нодой. Что происходит с одной нодой. Вот про это мы с вами и поговорим.

Начать бы хотелось вот с чего. Э, недавно DataБК купили openсоourceную базу данных Neon 1 млрд. За 1 млрд. Если мы посмотрим, а что такое неон? А что такое неон? Ne - это у нас серверс постгress, который можно скейлить, бранчить и так далее. Хорошо. Но у нас есть, например, ЮBйт, который тоже серверле погрес. И ещё каждый год у нас происходит тонны сделок. У нас происходят тонны сделок, которые связаны с базами данных. Например, например, например, например, пожалуйста, вот, вот появились новые какие-то базы данных. Вот кто-то кого-то купил. Вот произошло финансирование 10 млрд, 8 млн, 8 млн, 9 млн, 12 млн, 24 млн. Недавно была новость Дотабрис кого-то купил за 250 млн. В общем, в база данных постоянно что-то происходит. А хочется понять, а за что деньги-то платится, почему это так дорого стоит, почему это так много стоит. Но типа у нас уже есть условные постгрес, не знаю, my, зачем нам появляется ещё база данных, ещё база данных, ещё база данных.

И чтобы ответить на эти вопросы и чтобы, когда в следующий раз выбирали для себя какое-нибудь новое фнси решение, да, или увидели на Hacker News какую-нибуд новую статью про новую базу данных, которая решает все ваши проблемы, вы могли открыть их landing page, открыть их оферинг и прочитать, что они на самом деле вам предлагают. Для этого нам нужно разобраться, что происходит в одной ноде.

Значит, давайте сначала подумаем, а для чего нам вообще нужны DBMS, то есть database management system или там на русском систему управления базами данных. Почему мы не можем просто всё хранить в файликах? Просто давайте всё хранить в Экселе, да, и всё. Просто будем хранить всё в Экселе ещё как DBMS придумали и так далее, потому что DBMS нам даёт ключевую функциональность, которую реализовать на файлах нам было бы сложно, да? Например, если это были бы файлы, мы на каждый файл писали там свою программу, как это всё распартить, там, допустим, CSV. Если бы поменялась условно схема, нам нужно было бы переписывать вот эту программу, которую у нас парси, да, там поменяли как-то формат, тоже бы пришлось переписывать.

Система управления базами данных нам даёт data independence, то есть мы не зависим от того, как там хранятся наши файлы. То есть для нас есть условно постгрес. Мы в него кидаем данные, мы с него забираем данные, как он у себя хранит, там раскладывает по директориям, там файлы бьёт на PйG. Нас это ничего не интересует. Мы знаем, что вот у нас есть такая абстракция, хранилище данных. Мы в неё закидываем данные, мы из неё забираем данные.

Дальше, что она нам даёт? Она нам даёт concurrнcy control. Что имеется в виду? Когда несколько пользователей одновременно что-то делают, когда идёт какой-то транзакционный workкloadло, там все начинают пытаться дёргать одну один и тот же атрибут, менять, как нам это всё правильно зарезовить. Там у нас идёт концерт, не знаю, Тревиса Скотта, все покупают билеты, кому дать билет, кому не не дать билет, что с этим делать. То есть система управления базами данных за нас может часть этих проблем забрать. Или нам явно сказать, что там вот здесь есть проблема, тебе её нужно решить как-нибудь, да, с конкурентным доступом. В случае с файлами там 10 человек, э, фиксят один файл, потом как это сохранить, там сохранять какие-то ревизии, что с этим делать, как потом это всё слить в одно. Постоянно появляется проблема, система проблем базами данных часть этих проблем от нас забирает. Про то, как она это делает и какие могут возникнуть проблемы, мы с вами поговорим позже.

Значит, Crash Recovery. Что она делает? Она у нас данные хранятся в памяти. Понятно, что электричество выключили. Бм, всё из памяти всё исчезло. Система управления базами данных старается максимально вас обезопасить от таких кейсов. То есть она ведёт какой-нибудь там есть какой-нибудь recovery менеджер, она ведёт какой-нибудь WR a headadlog, который за вас сохранит эти данные на персистентный диск. И потом в следующий раз, когда вы живёте, она у вас до какого-то там валидного состояния откатит, да, и у вас не будет там наполовину повисших транзакций, к примеру.

Также она даёт вам Security Access Contроol. То есть, например, эту часть базы данных ты можешь смотреть, эту часть базы данных ты не можешь смотреть, там пришёл джун проект, он схему не может поменять, этот человек может поменять, этот может смотреть, этот не может смотреть. Вот весь условный Airbag, да, Security Access Control система управления базовым данных нам тоже может предоставить.

Давайте посмотрим. на архитектуру классической, условно, там, реляционной СУБД, да, и попробуем сами свою же придумать. Но как мы будем придумывать? Мы будем придумывать не с нуля, а мы будем опираться на существующее решения. И когда у нас там где-то затык или что-то у нас там где-то не хватает, мы будем подглядывать, а как это делается в других местах, а как это делается в реальных системах. Вот. То есть ещё раз, мы сейчас не строим, то есть не будет такого, что вы посмотрели эту лекцию, и вы сможете построить там с нуля свой сторыжко компонент, но вы будете знать, какие движущиеся части там есть и как они все вместе складываются в общий пазл.

Давайте посмотрим, а какие бывают архитектуры. Значит, архитектуру классической реалиционной системы управления базами данных можно представить вот так. Что у нас здесь есть? У нас есть SQL команда. SQL команды нам приходят с нашего приложения там либо с командной строки, откуда угодно. Вот нам приходят SQL команды, они попадают в Query Evoluation Engine. Значит, про каждый из этих компонентов мы с вами будем в отдельности говорить. Они попадают в querer Evolution Engine. Что там происходит? Там происходит партинг запросов. Потом этот запрос бьётся на реляционные выражения. А потом из этих реляционных выражений строятся планы, выбирается типа эквивалентные планы сравниваются, выбирается тот из них, который там самый оптимальный в зависимости там от статистики данных и от того там кто сколько операций переберёт. На это мы тоже дальше посмотрим. И мы говорим: "Вот, вот этот план тебе нужно исполнить".

Дальше этот план а у нас работает. Он там задействует какие-то методы, которые может, ну, там, например, подёргает индекс или знает, что там вот это будет лежать вот тут, это будет лежать вот тут, вот это мне можно заиспользовать. Параллельно с ним работает concurn control, transaction maner, logменеджер, который следит, какие сейчас активные транзакции, какая транзакция, там, например, если это какой-нибуд MVC, какая версионность, кто какие может видеть версии и так далее. Или там, если это какой-нибудь локинг, у кого сейчас на что лог висит. Recovery manager у нас ведёт врата, который пишет там вот такие данные, вот такие изменения, вот такие изменения, вот такие вот такие изменения произошли и скидывает их на диск. Вот про все эти компоненты в отдельности мы с вами подробнее ещё поговорим в следующих лекциях.

Значит, у нас есть буферменеджер, который таскает с диска в память, и есть disk space Space Manager, который уже отвечает за, грубо говоря, то, как у меня байтики складываются на диске. И вот сама сами данные у нас в виде индекс файлов, датафайлов и систем каталога. Значит, это классическая реляционная система управления базами данных.

Давайте посмотрим, а какие есть ещё варианты. Есть, например, вот такой вариант, который делает как RDB. Значит, у них есть три компонента. Это Gateway, Executor, KV. И каждый из этих архитектура у нас разбивается на слои. И каждый из этих компонентов выполняет роль нескольких слоёв. Например, КВcation Storage. То есть он там то, как мы храним байты, то, как мы там правильно варим VCC, как мы это всё раскидываем, как мы это всё синкаем. SQL экзекутер там за транзакции, за то, как это всё распределить правильно эту транзакцию, да, там если это какая-нибудь транзакция, которая задействует несколько нот. SQL Gitway отвечает за то, чтобы нам этот SQL запрос разобрать уже.

Вот, к примеру, тот же неон, который вот если вы помните, в начале была новость, купили за очень много денег, что делает неон? Ne, условно условно, что делает неон, он разбивает постгрес на два компонента: на компьютер и на storage, да? То есть он обманывает Постгрес, и Постгрес условно думает, что он работает так же, как он обычно работает. А на самом деле нет. На самом деле под ним лежит условный Amazon EBS, да, какой-нибуд там distributed block storage, а Postgress думает, что он работает так же, как он до этого работал. Как они это достигают? Они достигают тем, что они перехватывают вот этот recovery сообщения Wstream и уже сами в свой кастомный storage, который они написали, уже хранят, распределяют и с помощью этого они могут версионировать его, например. То вот вот их основная фича, там бранчинг версионирования, всё благодаря этому они уже могут сделать. Вот про то, как примерно выглядит object storage, да, мы с вами тоже поговорим.

Значит, следующее - это TDB. TDB тоже разбивается на несколько слоёв. У нас есть условные TKV, которые на самом деле LSM Storage Rox DB. Потом каждый вот этот кв друг с другом синкается с помощью рафта и они уже состоят в кластере, в котором мы посылаем наши запросы. Вот все вот эти движущие компоненты мы с вами будем разбирать, чтобы когда вы в следующий раз увидели что-то вроде такого или вот такого или вот такого, вы могли понять, а что здесь написано, а что имеется в виду.

Ну давайте начнём с самого начала. Начнём со сторжи. Значит, стож. Давайте подумаем, а как нам с вами складывать байтики? Как нам с вами складывать байтики? Например, у меня есть в базе данных таблица users, да? И что мне делать? Как мне эту таблицу users представить у себя на диске? Давайте с вами подумаем.

Значит, мы подумали, подумали и подсмотрим решение у inadb. Значит, и на DB. Что это? INDB - это один из движков MyQL. Что делает inb? INDB, вот здесь интересно написано table per file. То есть, например, у нас есть таблица users. Таблица users, это будет один файл в проприетарном формате, там EBD. Хорошо. Таблица, там, не знаю, Orders. Вот второй файл. Давайте, давайте мы эту идею с вами заберём себе. Значит, у нас есть таблица users. У нас есть с вами таблица users, и это у нас отдельный файл. Хорошо.

Значит, теперь в этот файл, что мы хотим в стоage слее? Мы хотим с этого файла уметь забирать наши записи. То есть кто-то нам будет говорить: "Отдай мне с этого файла запись какую-нибудь там, не знаю, один". И в этот файл нам кто-то будет добавлять записи. Например, добавь там 10, а-э, не знаю, Влад семь. Угу. Хорошо. Теперь что нам делать? Теперь что нам делать? Теперь нам надо подумать, а куда записывать в этот файл, да? То есть нам надо где-то тречить, где у нас конец файла, где у нас есть свободное место файле или там кто-то когда-то что-то вычитывает и вдруг они вычитывают один и тот же кусок, а оба начинают его редактировать. Как нам заменеджить правильно этот файл, да? То есть нам их складывать друг за другом, нам их складывать там, не знаю, через один. Что что нам с этим делать?

Значит, мы подсмотрим идею, которая называется pagйд. Что мы сделаем? Мы этот файл разобьём на блоке, на пейджи, где каждая пейджа будет фиксированного размера. Например, там 4 Кб, 8 Кб, 16 Кб. Вот кто-то подумает про PG операционной системы. Если вы подумали про PG операционной системы, то это здорово. Если нет, то тоже всё хорошо. Но размер этих Page не обязательно должен мапиться с размером операционной системы. Вот. А база данных лучше понимает, какой размер PG ей будет оптимален для её ворклоуда. Вот. Хорошо.

Значит, теперь у нас есть PG. Это здорово. Теперь, когда мы хотим достать какие-то данные, мы, например, можем сказать: "Эти данные лежат там в первой, в третьей PG, на второй позиции. Пожалуйста, вот их забери". Мы их типа раз, раз, раз заберём. Если кто-то другой захочет их же забрать, а мы там с ними что-то делаем, мы будем знать, что там тебе придётся подождать. Или там кто-то забрал вот эти три пейджи, кому-то нужны там вот эти ещё пейджи. Мы знаем, что эта пейджа у нас как бы уже есть, и мы её можем, грубо говоря, там пошарить, например. Найс. Теперь у нас есть какой-то логический юнит, с которым мы можем работать.

А давайте теперь думать, а как нам писать данные в каждую пейджу? Как нам складывать данные в каждую пейджу? Значит, это уже интересно. Вот у нас есть пейджа наша, да? То есть файл состоит из пейджей. Вот мы смотрим одну пейджу. Вот у нас есть наша пейджа. Что нам в ней нужно хранить? Ну, наверное, наверное, нужно хранить какой-то хедер. Какой-то хедер, где мы будем следить, например, за чексуммой, проверять, э, пейджа разбилась, не разбилась, когда мы её таскали с памяти на диск дисков память. Нам нужно что ещё посмотреть? Нам нужно посмотреть там что-нибудь, связанное с каким-то там свободным местом. Есть ли у нас свободное место, когда оно начинается, где оно заканчивается и так далее, и так далее. Плюс ещё там разные моменты, но пока, думаю, на этом остановимся.

Теперь, допустим, у меня все мои данные, да, все мои записи, которые я присылаю в базу, вот уже там запиши 10 Влад 7, они у меня фиксированный длины, да? Они у меня фиксированные длины, например, 10 Влад 7. Они у меня фиксированные длины. Тогда как мне их складывать в пейджу? Как мне их складывать в пейджу? Они все пускай весят 32 байта. Ну тогда, в принципе, в принципе я могу их складывать в PЖУ друг за другом. Я могу складывать в Pageu друг за другом. Одну запись положил, вторую запись положил, третью запись положил, четвёртую запись положил. Вроде всё найс. Теперь, если кто-то захочет спросить: "Отдай мне четвёртую запись". Да, размер хедера у нас фиксированный, размер одной записи у нас фиксированный. Мы можем сразу ему отдать там четвёртую запись, условно вот на забирай. Хорошо, это здорово.

Какие могут возникнуть проблемы? Проблемы могут возникнуть, когда, например, какая-нибудь запись вот здесь удалится, и у нас есть свободное место. То есть нам тут надо условно тречить, что вот это следующее свободное место, там вот тут свободное место, от неё тречить вот тут следующее свободное место, да? И там порядковый номер как-то у нас словно может сбиться. Теперь четвёртая, она на самом деле ниже. Придётся чучуть погулять. Но гулять от записи к записи нам не так сложно. Почему? Потому что она фиксированного размера и можем просто перескакивать 32 32 и следующую следующую следующую следующую запись забирать. Вроде в принципе всё о'кей, но понятно, что мы сталкиваемся с такой проблемой, да, допустим, а на хранение вот этого у меня уходит, не знаю, сколько, пускай будет 4 байта на хранение. Вот это у меня уходит там, не знаю, 8 байт. Но что делать с вот этим? Что делать с вот этим? Что делать с вот этим? Тут уже интересно.

Значит, мы можем для вот этого всегда с запасом дать какой-то фиксированный размер, да? Мы, например, говорим, что это всегда весит 255. Тогда вот, если у меня здесь написано просто Влад, всё остальное неиспользованное место, ну, мы просто тратим. Мы как бы себе упростили, что у нас все записи фиксированный длины, но тогда вот это всё место мы просто так израсходуем бесполезно. Понятно, что не самый лучший вариант, но если у нас начнут записи быть разных размеров, разных размеров, тогда по ним вот так гулять от одной к другой мы уже просто не сможем, потому что одна запись вот такой длины, другая запись вот такой длины, третья запись вот такой длины, вот такой, потом ещё длинная запись, и уже от одной записи к другой там сразу дать, например,чет на четвёртой позиции вот так мы не можем, потому что они разной длины. Плюс ещё нам нужно как-то понять, а когда закончилась эта запись, а когда началась другая запись? Или в рамках одной записи нам даже нужно понять, а когда начался этот атрибут, а закончился другой атрибут.

И вот как раз-таки с такими моментами мы подглядим, как можно это закодировать. Это можно закодировать следующим образом. Значит, смотрите, у нас уже есть, то есть что-то похожее условно делает прото. Значит, у нас уже есть схема, да? Мы пока что в реляционной базе данных. У нас есть схема. Мы знаем, что вот здесь у нас условно какой-то переменной длины айдишник. Вот здесь он у нас переменной длины фамилия. Вот здесь у меня переменной длины департамент. Вот здесь у меня фиксированная. Мы это знаем из нашей схемы, грубо говоря, как у нас вот каждая запись выглядит. Теперь, что мы делаем, когда у нас переменной длины? Мы говорим, вот здесь мы храним фиксированный заголовок и ему говорим, что вот хочешь найти этот атрибут переменной длины, иди в двадцать первый байт и пять байтов прочитай. Хочешь найти этот, иди в двадцать шестой байт и 10 байт прочитай. Хочешь этот, иди в тридцать шестой и 10 байт прочитай. Этот вот здесь прямо лежит, потому что он фиксированного размера. Хорошо. Хорошо. Теперь мы можем, например, с этой записи сразу забрать там условно третий атрибут, потому что мы знаем, что он переменной длины. Здесь будет там три фиксированных хедера. Вот он третий. Мы раз пойдём и прочитаем. Неплохо. Уже лучше. Уже лучше. Хотя бы мы теперь можем понять, где один атрибут заканчивается, начинается другой, там, где третий, десятый. Одну запись от другой хотя бы можем как-то различить. Но проблема с тем, что они будут лежать, они будут лежать и сразу, например, взять четвёртую, да, ну мы пока что не можем сразу взять четвёртую мы пока что не можем, потому что они все переменной длины.

Плюс ещё может быть, что какой-то атрибут какой-то атрибут просто, ну, грубо говоря, не залазит в нашу пейджу. Просто он типа больше, чем размер пейджи, да? Что-то вы там решили в нём хранить интересно. не знаю, Jйсо какой-нибудь огроменный или там, э, фильм закодировали в BS64, решили хранить. Вот эти моменты мы решаем с помощью Overflow Payg. То есть в оригинальной Page мы просто будем типа ссылаться, что о'кей, хочешь эти данные, они вон там лежат, иди их возьми. То есть это может ссылаться в workflow pageu в постгресе. Это называется у нас, а, toast toast. Вот overсайized атрибут storage техchne. Как раз-таки для вот этого. Как раз-таки для вот этого. Хорошо. О'кей. Эту проблему мы тоже там как-то решили, но теперь у нас проблема, когда они разной длины, а мы хотим условно забрать там с вот этой пейджи, да, это, допустим, это там третья пейджа, мы хотим дай мне третью пейджу, вторую запись. Вот так быстро ответить мы на этот вопрос, к сожалению, не можем.

Для этого мы добавляем ещё один слой индирекции, да? То есть, что мы с вами делаем? Что мы с вами делаем? Мы берём pageйджу. Мы берём pageйджу. У неё есть фиксированный headдер. А потом для каждой записи мы тоже делаем свой headдер. Вот так фиксированной длины. Раз, раз, раз, раз, раз. А каждый из этих хедеров хедеры растут из начала в конец PG, а из конца в начало Page у нас растут наши данные. И мы можем сказать: "Вот этот headдер указывает вот сюда на эту запись. Вот этот указывает вот сюда. Там, допустим, вот этот указывает вот сюда. Вот этот указывает вот сюда. И теперь, когда нам говорят: "Дай мне с этой PG четвёртую запись", мы можем сразу, вот это фиксированной длины, вот это каждый из них фиксированной длины, можем сразу найти четвёртый и ткнуть. Вот он, забирай в этой же Pйдже. И ровно такой же подход, ровно такой же подход у нас с вами использует Postгрес. Ровно такой же подход у нас с вами использует Postgrгess. Вот, пожалуйста. То есть у нас есть каждая, у каждой PG есть свой какой-то, где хранится чек сумма. LSN - это для WR head lлоog версия, там флаги. Lower uper. Прикольно. Это что? Lower upper это где заканчиваются хедеры, где заканчиваются сами у нас уже записи. Что с помощью этого можем сделать? Проверить, сколько у нас свободного пространства, да? То есть они растут вот отсюда, эти растут вот отсюда-сюда. И можем проверить, сколько у нас свободного пространства осталось, типа, стоит ли в эту pageйджу что-то писать. Постгрес использует ровно такой же подход. Пожалуйста. Вот мы с вами типа придумали постгресса. Плюс ещё у каждого хедера этой записи, у каждого хедера записи есть свои поля, свой хедер, где мы внутри храним, например, для MVC, какую транзакцию он может, какую транзакцию он не может. Там ссылка на следующую запись, да, то есть потому что MVC хранит несколько за несколько версий одного одной и той же записи. Вот и другие моменты, которые мы с вами посмотрим. И также вот момент, что у самой PG тоже может быть headдер. Он фиксированного размера, 24 байта, и в нём уже вот там чек сумма. Ну, это мы с вами видели на другой картинке. Хорошо. Супер отлично. Супер отлично.

Теперь может другой момент у нас возникнуть. Теперь как нам достать с третье PG четвёртую запись? Пожалуйста, каждый день. Но возник другой момент, что мы помним, что записи у нас переменной длины, да? И тогда может случиться вот такая ситуация. Вот у меня была запись, вот была запись, вот была запись, вот была запись. Это я удалил, это я удалил. Вот это хочу вставить. И по идее на него место есть, да? На него место есть, по идее. Ну, то есть, допустим, если это весит восемь, это весит на него место есть. Но что нам придётся сделать? нам придётся тогда это удалить, это удалить, а потом их друг с другом передвинуть, да, передвинуть свободное пространство. То есть вот эту там сдвинуть направо или вот эту сдвинуть налево. Что-то придётся с этим сделать. Но когда мы это будем делать, что нам придётся делать? Нам придётся и вот эти все указатели пересобирать. А вдруг кто-то работает с этими данными? Тогда нам придётся это всё подлочить и посмотреть, чтобы никто их параллельно там не вычитывал и не модифицировал. Проблема. И это проблема.

И как раз-таки такой проблемой с мёртвыми туплами у нас занимается вакуум. Вакуум - это условный гарбадж коллектор в вашем сторадже, который вот vacum reclaim storage occupied by tles in normal postgress operation tles are deleted or absoluted by update are not physically removed. То есть мы их не удаляем, но мы их просто помечаем, что вот их надо убрать. И в следующий раз, когда у нас вакуум отрабатывает, он их убирает. Что он делает там? А дальше уже в вакуум вы можете в зависимости от того, как вы его затюнили, то есть он там либо всё это пишет в новую пейджу, либо там в этойже двигает. Вот это можете уже отдельно почитать, если вам интересно. Хорошо. Здорово. То есть, в принципе, всеми вопросами, которые у нас могут возникнуть в рамках стореджа, мы плюс-минус разобрались. Мы плюс-минус разобрались. Единственное, что мы не разобрали, это какие есть у нас альтернативы, да? Но на альтернативы мы с вами посмотрим позже. Посмотрим позже.

Значит, что ещё? Вот вы часто могли слышать, что есть там row oriented, colum oriented, да? Или там говорят колоночные базы, колоночные базы. Вот покажу на абстрактном примере, что почему, например, есть отдельный подкласс, да, баз данных, которые работают с коло с колонками. И как бы что это нам даёт? Вот давайте возьмём на таком примере, вспомним, как у нас сейчас хранятся. Вот у нас есть PG, у нас есть PG. Если вы подумали про клиck house, это рядом, но клиck использует чуть-чуть другой тип стоджа. Но вот мы сейчас берём абстрактны. Вот у меня есть PG, в нём есть записи. В нём есть записи. И записи хранятся вот так: 10 Влад семь, да? Допустим, семь - это там привлекательность по стобалльной шкале. И у меня есть ещё другие записи, там, не знаю, какой-нибудь там Олег 5, не знаю, какой-нибудь там Игорь

90, вот и там бла-бла-блаблаблабла. Ещё у меня много, много много миллион, миллион записей. Вот.

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

Тогда какая проблема? Вспомним, как это всё у нас лежит. Чтобы прочитать вот это, мне придётся из PG выгрести вот так целиком. Да, мне придётся выгрести page, а потом из page выгрести вот это. Но мне по сути нужно только это число. А зачем я вот это забрал всё? Зачем я вот это всё забрал? Оно мне не нужно. И вот тут я лишнего набрал. И вот тут я лишнего набрал. И вот тут я лишнего набрал. И вот здесь, и вот здесь, и вот здесь, и здесь. И вот здесь я столько лишнего набрал. Хотя по факту меня только вот это интересует.

Как я могу этот вопрос решить? Я могу этот вопрос решить так, что я переорганизуюсь тоже. И теперь я буду хранить все атрибуты рядом. одного типа, бла-бла-бла-бла-бла. И вот здесь ID. Вот я теперь храню все атрибуты рядом. И теперь, когда мне нужно, например, посчитать вот это, я буду их выгребать, и они все реально будут рядом лежать.

Что я могу ещё сделать теперь? Поскольку это все атрибуты одного типа и они лежат рядом, я могу здесь уже сделать какое-нибудь там сжатие, какое-нибудь кодирование. Плюс я ещё могу использовать векторные операции. Я могу там параллельны, если это сумма, да, то сумма у нас условно коммутативная, я могу там вот это сложить, с этим сложить параллельно. То есть могу различные другие оптимизации делать. И когда я выгребаю данные, я буду выгребать по факту только то, что мне нужно, а вот без вот этих вот лишних атрибутов. О'кей. для подсчёта чего-то. И это пушка. И это пушка.

Но, но, но когда возникает проблема, проблема возникает, когда нам нужно будет собрать этот эту запись обратно. То есть, когда, например, я хочу узнать, а вот это кто? Я смотрю, что он здесь на четвёртой позиции, да? Я должен найти здесь кто на четвёртой позиции, здесь кто на четвёртой позиции. Там условно, если там что-то происходит, возможно, их всех подлочить и потом вот это реконструировать. Вот так собрать. А, допустим, оно здесь пожато, её надо разжать и выдать, да? То есть поэтому у нас условно есть аналитический workклоуд, а есть транзакционный workкloadд. И поэтому для аналитического ворклоуда там подходит один тип стоджа, для транзакционного ворклоуда подходит другой тип стоджа, потому что то, как хранятся данные, влияет напрямую на то, как мы с ними работаем. О'кей. Надеюсь, этот момент стал вам более понятен. То есть вот column oriented, мы храним все атрибуты вот так рядышком. Row oented мы храним запись. Хорошо. Хорошо.

Значит, с этим слоем там датафайл мы как-то более-менее с вами разобрались. Теперь что интересно? Теперь здесь есть какой-то systemм-каталог. А что такое systemкаталог? Что такое systemталог? Хмм, надо подумать. Делаю вид, что я думаю. Значит, system катаalog - это, по сути, директория, которая хранит методанные о том, где что находится. Например, вот эта таблица там условно постгреси лежит в этой папке, в этой директории, в этих файлах. На эту таблицу вот такая схема. На эту таблицу навешаны вот такие индексы. Эту таблицу можно там читать вот этим вот этим вот этим юзером. Или там вот этот индекс находится в вот этом файле, вот это находится вот здесь. То есть метаданные о том, где хранятся ваши данные, там сколько, например, здесь есть свободного места, сколько там хранится записей. Вот все метаданные мы можем хранить в этой директории. Хорошо. Хорошо.

Значит, теперь интересное. Теперь интересное. Смотрите, нам нужно данные с диска таскать в память. Нам нужно данные с диска таскать в память. Почему мы это с вами хотим делать? Почему мы с вами это хотим делать? Почему мы хотим их с диска таскать в память? А как аналогию скажу, например, с вашим приложением, обычным веб-приложением, которое вы разрабатываете, да? Вы там обычно добавляете какой-нибудь кэш в виде редиса и прочее, но сюда, если вы добавляете кэш, у вас тоже возникают различные проблемки там с инвалидацией и прочее. Вот здесь мы тоже что-то подобное увидим. Ну вот одна из причин, например, что достать это на 2025 год числа Planet Scale. Ссылка будет, значит, достать что-то из памяти. Roundтрип - это 100 наносекунд. Достать что-то из диска - это 50 микросекунд. Чтобы вы представляли скейл, как это происходит. То есть вот мы говорим про вот такой порядок, понимаете? То есть пока вы что-то достанете из диска, в памяти уже вообще уже уже там на порядок. Мы уже всё уже закончили, уже домой пошли, но при этом памяти у нас меньше и память у нас волатильная. Что значит волатильная? Это значит, что когда условно выключится электричество, да, что часто происходит в Узбекистане, то все данные из вашей памяти пропадут. Поэтому нам нужно как-то хитро работать с ними в памяти, да, но при этом не забывать их скидывать на диск. Не забывайте скидывать на диск. И как раз-таки за вот такие моментики, за вот такие моментики у нас будет с вами отвечать буфер пулol. Отвечать буфер пулol.

Значит, что может делать буфер pool? Буфер пулol может затягивать страницы page с диска себе в память. При этом он ещё может выполнять функциональность какую? Он, например, видит ваш запрос, да, что вы делаете какой-нибудь там сексн, и он может заранее, например, заприфечить страницы, которые вам будут нужны. Либо онвидит, что несколько запросов хотят одну и ту же страницу, он её не будет выталкивать из буферпула, а между ними условно пошарит. Или, например, э какая-то страница часто используемая, например, директория или там корень индекса, он её может взять и запинить. Он её может пометить, что она грязная, значит, её типа там нам нужно, это зависит от стил полиса. Это мы больше с вами поговорим, что с ней нужно сделать. Он может там хранить на ней, кто кто сейчас её залочил, кому она сейчас нужна, там эксклюзивный лок на ней стоит, лок на ней стоит. Про это мы тоже с вами дальше поговорим. То есть буферpol выполняет не только базовую функциональность, что это просто кэш. То есть он выполняет ещё различные такие моментики.

Но, но, но, но понятное дело, что, предположим, у меня там, а, на диске эта база уже разрослась, что она занимает, не знаю, терабайты, но памяти у меня нет терабайтов. Памяти у меня ограниченное количество. Тогда возникает вопрос: а кого выталкивать? Кого выталкивать из памяти? Кого выталкивать из памяти? Его, его, его его. Кого? Не туда ткнул. Его его его его. Кого? Кого вытолкнуть? Можно взять самую простую полиси. Можно взять Фифо. Первый пришёл, первый ушёл. Хорошо, тогда мы первым, например, затолкаем себе каталог индексы. Мы их первыми же и выгоним, когда у нас идёт обычный там селект звёздочек какой-нибуд секскан. Плохо.

А есть другая полиси. Есть полиси, которая называется.ru есть задача на лидкоде. Я вам всем её советую порешать. Либо можете найти, у меня в курсе по алгоритму. Шучу. Значит, смотрите, что такое LRU. LRU - это list recently used. На русский переводится не очень хорошо, но least recently used - это наименее недавно использованный. Наименее недавно использованный или типа тот, кого давно трогали, грубо говоря, тот, кого давно трогали. Например, вот у меня есть кэш размером три. Я добавляю 1 О'кей. Я его недавно потрогал. Я добавляю 220. О'кей, только потрогал. Я добавляю 330. О'кей. Только потрогал. Теперь, когда я захочу добавить 440, у меня уже нет места в кше моём. Кого-то из них надо толкнуть. Кого толкнуть? Толкну я 10. Почему? Потому что я добавлял 10, 20, 30. И получается 10 я самое давнее, кого я трогал. Но если я сейчас возьму и потрогаю 10, да, 11, то я его освежу, типа вот я вот я тебя потрогал, и тогда у нас появится 20. И если я потрогаю три, а за ним потрогаю два, то кто у нас опять стал самый давно нетроганный, кроме Влада? 10. Всё верно. И теперь, когда я буду добавлять новую запись, она у меня вытолкнется отсюда. Хорошо? Значит, это клёвое полюси. То есть, условно, у нас будут какие-нибудь индексы, которые мы будем часто использовать или там, э, табличка какая-нибудь популярная, которую мы часто будем пользовать. Она у нас, в принципе, всегда будет прогрета.

А проблема с LRU, так называемая проблема sequential fluding. Что это значит? sequential floading. Если простыми словами объяснять, что у меня что-то было вот здесь, то, что мне нужно, да, потом это бы я бы вот здесь где-нибудь заиспользовал бы вообще с кайфом, да, и вот здесь бы заиспользовал, да, вообще оно мне нужно. Но вот здесь, допустим, происходит какой-нибудь огромный сексскан. Огромный сексскан, который посчитает, ну, не знаю, какою сумму атрибутов, да, какое-нибудь такое одноразовое значение. Но вот этот секскан, он будет выполняться, и пока он будет выполняться, он начнёт прогревать, прогревать, прогревать, прогревать, прогревать, прогревать. И и получится, что они все те, кого недавно потрогали. А вот эти окажутся, что их давно не трогали, они вытолкнутся. Хотя они бы нам вообще с кайфом вот здесь пригодились. Вот это проблема. А можете про неё ещё прочитать. Называется сек флудинг. Найс, найс, найс, найс, найс, найс.

Теперь, значит, что мы с вами поняли? Мы с вами увидели, значит, что там, как мы что храним на диске, да, как мы что-то там достаём в память себе прогреваем какие-то там каталоги, которые нам говорят, где что искать. Но, но, но, но, но а кто приходит к нам в сторедж и говорит, что если я хочу найти вот эту запись, она лежит в этой пейдже вот в таком-то отступе. Кто это? Кто ты? Кто кто ты воин? Кто этим занимается? Да и вообще, как мы можем сейчас это решать? Допустим, мы мы хотим найти что-нибудь там из таблички с определённым там айдишником или атрибутом. Как мы это можем сделать? Ну, можем типа выгрез вообще всю таблицу, перебрать и найти то, что нам нужно. А можем можем можем использовать определённые механизмы структуры данных, которые ускорят этот поиск, доступ к нужным нам данным или по-другому. Йя дробь, спойлер арт, индексы. Всё верно. Подумайте, какие индексы вы знаете. Какие индексы вы знаете? Какие индексы вы знаете? Хорошо, вы подумали, значит.

Но давайте разберёмся сначала с основной терминологией. Значит, какие могут быть индексы? Индексы могут быть кластеризованные, не кластеризованные. Значит, что значит кластеризованный? Кластеризованный - это значит индекс диктует то, в каком порядке будут храниться записи в файлах. Вот прямо типа то, как они хранятся, да, то как они хранятся в индексе, условно. Также и диктуется порядок здесь. Некластерные - это когда такой порядок не диктуется. Например, например, например, в MySQL в NDB primary индекс кластерный, он будет диктовать то, как хранятся в каком порядке файла. А в постгресе используется хипа куча организации файлов, и они у вас в рандомном порядке. У вас есть там primary индекс, да, который там задаёт primary key, но этот primary индекс у вас отвечает только за Unique constraint, чтобы вы благодаря нему могли отличать одну запись от другой. Одну запись от другой, да, условный какой-нибудь там автоинкремент, но за порядок записей он нам не даёт.

Зачем нам нужны, например, записи в порядке? Потому что, если у нас записи лежат в порядке индекса, мы можем построить разряженный индекс. Что нам даёт разряженный индекс? Вот посмотрим. Вот они хранятся в порядке айдишников, да? У нас есть плотный и разряженный spars den indкс. Значит, плотный индекс мапит один к одному записи. Разряженный индекс может мапить диапазоны. Например, вот здесь записи находятся с 10101 до там 3243. Вот здесь 3 2 3 4 3 до 76 766. Что нам это даёт? Что нам это даёт? Благодаря этому мы можем сделать сам индекс меньше и обновлять его реже. Но мы это можем сделать только когда у меня вот здесь есть порядок. Видите, они отсортированы по айдишником. Понятно, что если порядка нет, то вот этот диапазон нам ничего не даст. Здесь может быть любое рандомное значение. Дальше мы можем строить иерархию из этих разряженных индексов, да, там, чтоб ещё измельчить, но это уже специфика.

Что такое Secondary икс? Значит, secondary индекс - это когда вы ищете по какому-нибудь другому атрибуту. Например, я ищу не по айдишнику, я ищу по, не знаю, почему, я ищу по какому-нибудь там computer science департамента, по какому-нибуд департаменту, где он работает. Я ещё по какой-нибудь зарплате, я ищу по фамилии, что-нибудь такое, да? То есть, если у вас условно есть какой-то, э, прай key, а вы ищете не по нему, а ищете по какому-то вторичному признаку, да, то вы используете secondнary indкс. Значит, о'кей. Как он может быть устроен? Он может быть устроен так, что он либо будет указывать также, где найти конкретно эту pageu эту запись, да? Но тогда какая проблема? Тогда, если будет работать вакуум, потом надо будет все индексы вот здесь поменять. Ээ когда они переедут, где кто находился. Ещё какая проблема есть? Ещё какая проблема есть? Подумайте. Либо второй вариант, хранить ссылку на primary индекс. То есть мы говорим: "Вот эта запись, это там условно 151 332 343 это запись вот эти, это запись вот эти, это запись вот эти". Тогда какая проблема? Тогда если где-нибудь туплы в PG переедут, вам ничего обновлять в своём индексе не надо, да? Но у вас добавляется слой индирекция, что вам нужно сходить потом ещё в primary индекс. Хорошо.

Значит, одни из самых популярных индексов, которые можно назвать, это шнкс и B3. Давайте посмотрим с вами на Шиндекс для начала. Что такое шдекс? Для того, чтобы разобраться, как работает шдекс, давайте посмотрим, как работает мапа. Я вам советую посмотреть видео на моём YouTube канале или где-нибудь ещё, но давайте вкратце объясню. Значит, у вас есть какое-то значение X, вы его пропускаете через хэш-функцию, оно вам говорит, куда это положить, условно, в какой бакет, да? Вот сюда, вот сюда или вот сюда. Теперь, если, например, оно попало вот сюда, а там же что-то было, какие есть варианты? Есть вариант вот здесь их заченить и хранить несколько значений, тогда какая проблема? Если у меня хэш-функция неравномерно распределяет, да, или данные так распределены, то у меня может получиться, что все они попадают в один бакет, и они будут друг за другом, друг за другом. И тогда мы вот от хэшфункции получим, что у нас линию занимает, да, оn, хотя мы хотим это доставать за за константу. Какая есть другая другой вариант? Есть вариант делать, что если вот здесь занято, давай напишем в следующий бакет. Но тогда может быть такой например порядок добавления, что все сначала добавились не в свои бакеты, а когда ребята придут уже в свои бакеты, там уже будут заняты, и они начнут ещё дальше переезжать. Есть вариант добавить вторую хэш-функцию. Есть вариант добавить, а, например, extendable hasшиing. Что это значит? Это, например, вы бьёте какой-то префикс и сначала берёте по первому биту префикса выбираете, куда она пойдёт. В первый, второй бакет. Как только там место закончилось, вы берёте уже вто следующее значение в префиксе и разбиваете в какой из четырёх. А дальше там в какой из восьми, дальше в какой там из шестнадцати. Вот. То есть вы всегда расширяете префикс, куда она у вас пойдёт. Хорошо.

Значит, для чего хороша хэш-функция? Хэш-функция хороша, когда мы хотим найти конкретное значение. Конкретное значение. Например, я хочу найти computer science. Computer science. кто работает в computer science. О'кей, на этот атрибут мы навесили, условно хэш-индекс. Мы пропустили через хэш-функцию. Она нам скажет: "О'кей, вот эти ребята там, вот эти адишники дватри там восемь работают в компьютер science. Nice.

Когда плохо работает ш хэш индекс хэш индекс плохо работает, когда нам нужно найти что-нибудь, например, кто зарабатывает больше 7.000. Кто зарабатывает больше 7.000? Почему? Потому что порядок того, как данные сложатся с хэш-функцией, да, нам никто не гарантирует. Нам никто не гарантирует. И поэтому, чтобы найти те, кто больше 7.000, что мне нужно делать? Мне нужно будет 7.000 пропустить через хэш-функцию. Найти о'кей, вот эти, вот эти, вот эти ребята. 7.0001, 7.0002, 7.003, 7.004. То есть каждый из этих чисел нужно будет пропускать и смотреть. Какой из этого вывод? Когда у нас идёт, что нам нужно точечно доставать какие-то конкретные данные, да, по какому-то конкретному значению, тогда ш супер хорошо. Но когда нам нужно доставать какие-то ренжи диапазоны, тогда у нас уже идёт поплава. Хорошо.

Значит, наиболее распространённый и везде использованный индекс и там возможный индекс по умолчанию, который вы всегда видите - это B + 3. Давайте с вами поговорим про B + 3. Давайте мы сначала с вами посмотрим, как работает B3, а потом посмотрим, как работает B + 3. Значит, будем рандомно добавлять какие-нибудь значения, да? Здесь я поставлю параметр пониже. Вот мы их рандомно добавили. Бам-бам-бам-бам-бам-бам-бам. Теперь, когда я хочу найти 761, как я могу это сделать? Я смотрю, 761 меньше 214. Нет, он между 214 768. Да, значит, я иду ниже. Он меньше 719. Нет, он больше. Да, иду направо, получаю 761. 761. Бам, бам, бам, бам. Найс. Я хочу найти 984. Я иду также сюда направо, сюда направо. Вот его нахожу. И оно у нас так дальше растёт, растёт, растёт. Смотрите, когда получается интересный момент. Я хочу добавить 985. Здесь у меня стоит note 2. Здесь уже места нет. Что тогда мне делать? Чтобы вот добавить сюда, мне надо это разбить на две ноды, распределить между ними, а вот сюда добавить новый указатель. Да, что вот у меня появилась ещё одна нода с новым диапазоном. Давайте на это посмотрим. Бабам.

Но, но, но нам надо помнить, что каждая из вот этих нот, она тоже как-то у нас хранится. Она тоже у нас как-то хранится. То есть, условно, каждая эта нода у нас, допустим, отдельная пейджа. И то есть, чтобы просовершить вот эту операцию, мне нужно будет вот эту пейджу залочить, разбить на два, вот здесь залочить, вот здесь обновить и всё это проделать. Хорошо, больно. Довольно больно. Теперь я хочу добавить 921. Оно пойдёт вот сюда. А теперь я хочу добавить 922. Я хочу добавить 922. Что надо будет с этой нодой сделать? Что надо будет с эти с этой нодой сделать? Её нужно будет разделить на две, перераспределить. Ну, когда мы её разделим на две, сюда нужно повесить новый указатель. Здесь уже нет места для нового указателя. Значит, её надо разделить на две. Тогда сюда надо навесить новый указатель. А здесь тоже нет уже места, тогда надо её разделить на две и сюда навесить на указатель. И то есть, смотрите, я просто добавление 92 нам может стоить вот столько. 1 2 3 бабам. У нас почти всё дерево с корня перестроилось. Это супер больно. Помним, что вот это какая-нибудь педжа, вот это пейджа, вот это пейджа, вот это пейджа, вот это пейджа, вот это пейджа. Оно всё у нас вот так сейчас перераскидалось. Больно, больно, больно, больно.

Но, но что она нам даёт? Она нам даёт, что когда я хочу найти какое-то конкретное значение, я могу её найти за O log MN, где m - это сколько у меня фанаут, сколько у меня выходит из каждой ноды указателей, да? То есть там в бинарном дереве BST мы говорим: "Это log n"N, потому что мы имеем в виду log 2n, а здесь это log mn, где m - это фанаут, который сколько у меня выходит нот из и из сколько у меня выходит указателей из одной ноды. Хорошо, это больно. Но теперь, когда я хочу найти, например, все значения от 271 до 761, ну, о'кей, я иду вот сюда, беру бам 271, бам 688. Потом, к сожалению, придётся идти наверх. Потом придётся опять спускаться вниз. Вот это чуть неприятно. Вот это чуть неприятно. И плюс ещё, если мы здесь посмотрим, у нас значения хранятся иногда не только в листовых нодах, но ещё и хранятся вот здесь. Ещё и хранятся вот здесь. Это ещё больнее. Поэтому для этого у нас есть B + 3. И во всех базах данных используется B + 3. B + 3. Смотрите, что такое B + 3. У меня значения хранятся только в листочках. При этом у меня все значения друг с другом подшиты. Что имеется в виду? У меня есть указатель на соседнюю ноду. И теперь, когда я хочу достать что-нибудь от 176 до 429, я могу пойти слева направо, бабам, и за раз их забрать. Кайф. Вот это кайф.

Но какая у этого проблема? Когда я сюда, например, добавляю 388, оно пойдёт вот сюда. Я хочу добавить 389. Что мне придётся делать? 1 2 3 389. Вот сюда. Бабам. Опять пересобирать дерево. Но теперь, когда мы будем его пересобирать, нам нужно следить не только за родительскими связями, нам ещё нужно следить за вот этими указателями. Они тоже у нас пересобираются. Смотрите. Бабам. Это, конечно, более неприятно в реализации это гораздо сложнее окажется. Советую вам попробовать. Хорошо. Но зато теперь ренжсканы у нас просто берут и за раз прямо можем пропылесосить.

Теперь, что у нас хранится? Что я говорю под что у нас хранится вот здесь в листочках, в значениях? Значит, у нас есть вот такие варианты. У нас в листочках могут храниться либо указатели, то есть вот это можно найти в седьмой PG, а вSET 2. Ну тогда, когда они будут перемещаться, нам нужно будет здесь тоже обновить. Либо-либо это может быть вообще какой-нибудь index organized storage, где у меня в листочках хранятся прямо pageйджи со значениями. Page со значениями, да, хорошо, хорошо. Это мы с вами увидели.

Значит, какие ещё у нас могут быть индексы? То есть боль B +3 в том, что как некоторые записи у нас супербольные, супербольные, потому что, чтобы произвести вот эту операцию сейчас сюда 393, мне придётся лочить почти всё дерево для того, чтобы его потом правильно ребалансировать, правильно засптить эти синоды. Баба. То есть мы представляем, что вот это пейджа, вот это пейджа, вот это пейджа, вот это пейджа, вот это пейджа, вот это пейджа. Всё это придётся лощадь, потому что произойдёт модификация, да, и там вдруг кто-то другой работает в этом же дереве, и для него всё изменится. Поэтому надо сказать: "Слушай, я сейчас буду его пересобирать". Для этого есть оптимизации. Например, у нас есть BP3, да? То есть это вот оптимизация, что она нам предлагает? А нам предлагает рядом с каждой нодой не сразу её перестраивать, а хранить определённый буфер. Хранить определённый буфер. Хранить определённый буфер. И мы накапливаем эти изменения и потом либо там снизу с нуля перестраиваем, а либо либо там, ну сами решаем, что нам, когда где перестроить, да? То есть мы можем копить какой-то предел этих изменений. Вот. Но тогда проблема появляется с чтением, что нам надо будет тогда ещё проверить, а есть ли эта запись в этом буфере, плюс это всё правильно заменеджить. Хорошо. Хорошо.

Значит, какие у меня ещё бывают индексы? У меня может быть bitmap индекс. Что такое bitmap? Bitmap - это когда у вас есть атрибут, у которого фиксированное количество значений, да? То есть это не так, что он может принимать там миллиарды значений, а он принимает довольно фиксированное количество значений какое-нибуд там, да, то есть он принимает только mail, femil или там L1, L2, L3, L4, L5. И я хочу проверить, в этой таблице есть кто-нибудь FIL L2 или нет сразу. Как я могу это сделать? Как я могу это сделать? Смотрите, вот у меня здесь пять записей, пронумерованных с нуля, да? Что я делаю? Все, у кого mail, я ставлю бит один на этой позиции 1, значит, нулевой бит о и 1 2 третий бит о Что это значит? Это значит, у первой записи будет mail и у третьей записи будет mail. Fail 1 1. Вот 1 1 1. Ага. То же самое делать для L1, L2, L3, L4, L5. Для L1 я делаю здесь. единица, потому что на L1 и на второй позиции единица, потому что тоже L1. Например, L4. Почему здесь единица? Потому что вот третья запись - это L4. Хорошо. Что я теперь могу сделать? Если я хочу проверить, ес ли в этой табличке FIL L2, я могу взять вот эту маску, вот эту маску и сделать по битвой. И я делаю по битвой. И, у меня остаётся один, да, на второй позиции. Что это значит? Это значит, что на первой позиции, что первая позиция у нас будет FMIL L2. Ну, понятно, тогда проблема, если маска слишком длинная, мне надо будет выискивать вот эти биты,

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

Следующий индекс. Следующий индекс - это инвертированный индекс. Да. Для чего нам нужен инвертированный индекс? Например, у меня есть три песни. У меня есть три песни. И вот здесь я тебя так любил, ты от меня ушла. Любовь, любовь, любовь. Вот здесь там у подъезда мы стоим, но без тебя вот тут, а солнце как луна, твоя любовь ушла. Вот три песни. И теперь я хочу найти все песни, в которых было слово любовь. слово любовь и его производные, например, там lovers или там loves и что-нибудь подобное. Вот что мне придётся делать. Мне придётся идти и перелопачивать каждую песню и там искать, есть ли там такое слово, и в конце сказать, что да, о'кей, вот в первой песне было такое и в третьей песне было такое. Но у нас для этого есть инвертированный индекс, да? Это там апачалу в эластике, в постгресе у вас тоже есть инвертированный индекс. Что он нам позволяет делать? Он возьмёт, распарсит эти песни, вычистит слова на все похожие на производные и заранее создаст вот такого вида индекс. Что, например, слово абобаба в первой песне, в третьей песне, слово лов было во второй песне, в четвёртой песне, там слово XYZ встречалось у меня там в первой песне. Вот. То есть это инвертированный индекс. И теперь, когда вы хотите найти, например, лов, вы сразу будете знать, о'кей, это вторая и четвёртая песня. Это вторая и четвёртая песня.

Значит, мы живём в 2025 году, и теперь мы умеем ещё по-другому кое-что делать. Например, например, песня построена на метафорах, да? То есть он везде писал: "Ты как лягушка, а я как пруд, я скочу без тебя". Вот что-нибудь такое. То есть понятно, что он поёт про лягушку и пруд, но все мы поняли, что он поёт про любовь. Все мы поняли, что он поёт про любовь, но конкретного слова любовь там нет в тексте песни. Но смысл песни мы понимаем, что это про любовь. Значит, для этого, что у нас есть? Для этого у нас есть имбединги, да? Что вы можете сделать? Вы можете взять какую-то модель, нагенерировать имбединги, то есть флоу примерно вот такое. Это вот я сейчас говорю про раги, про векторные базы данных. Вы берёте, генерируетебединги через бединг модель, она нам даёт типа вектора. Она даёт вектора, то есть это массивы флоутов, да, что вот этот вот эта песня, она вот в этих векторах. Дальше, что вы делаете? Вы эти вектора мачите с метаданными, что там, о'кей, это вот это вот эта песня или там вот эта капучино и что-нибудь там что что уже вы хотите от вашего бизнеса, что вам надо, и суёте это векторной базы данных. А потом вы можете спросить у векторной базы данных, какая песня про любовь, и там происходит либо топка похожих результатов, либо там берётся там расстояние косинусов, смотрится как как какой вектор ближе. И уже по смыслу вы можете выгребать то, что вам нужно.

Хорошо. Значит, нам остался больнючий индекс. Нам остался больнючий индекс, а именно геоиндекс. А именно геоиндекс. Значит, приготовьтесь. Для этого мы возьмём R3. R3, да? То есть есть пост. Постгиз используется как раз-таки R3. Значит, что такое R3? Почему мы не можем использовать наши обычные индексы? Допустим, мы возьмём наш обычный какой-нибудь B3 композитный индекс, и мы хотим найти вот здесь у меня Y, вот здесь у меня X, вот здесь у меня Y, и я хочу найти, например, вот эти все кафешки между X и Y. Как у меня композитный индекс построится? Он отсортирует сначала по X, потом отсортирует по Y. Что мы получим? Мы получим 0,1 0, 03, 0,4, там 0,5, 11, 1 2 13 и бла-бла-бла-бла-бла-бла-бла-бла-бла. Но мы понимаем, что ближайшие кафешки это те, у которых там 44, 55, 66, 45. Но если мы построим вот такой обычный индекс, он как бы не понимает связь между этими двумя переменными. Но он просто их отсортирует по одному, потом по-другому, да? И нам придётся условно делать перебор и потом каждый или там каждый с каждым мерить расстояние, да, обычноя, а которое √ квадрат. Нехорошо. Или это не обязательно локация, это может быть, например, рост, вес, да, зависимость. И мы хотим там найти оптимальный рост вес, когда у меня есть зависимость от нескольких переменных. Плюс это может быть не две переменные, это может быть трёхмерное пространство, да? Там какой-нибудь болид формула 1 и там насколько шины и стёрты, там какая максимальная скорость, ещё что-то, там, какие-то параметры мы хотим найти в пересечении. Вот для таких задач у нас есть R3.

Значит, что такое R3? R3 - это условно B3, который понимает геометрию. Что имеется в виду? Что имеется в виду, когда я хочу найти, например, какой-нибудь R12, да, я себе рисую диапазон и говорю: "Это диапазон куда попал? В верхней иерархии в R1 или в R2?" Допустим, он попал в оба. Тогда иду там в левое подерево, в правое поддере, потом смотрю в этом поддере куда попал? В R3, R4, R5. Он там попал в R4, иду, достаю R12. Вот. Но у нас могут быть нахлёсты. У нас могут быть нахлёсты, да. И наша задача, задача R3- минимизировать эти нахлёсты. Потому что каждый раз, когда у нас происходит нахлёст, нам приходится перебирать типа лишнее под дерево, которое в котором наших значений нет. Если смотреть на карте, то это будет выглядеть вот так. Например, я хочу найти все кафешки, которые там все достопримечательности, которые находятся вот здесь. Я вот так рисую квадрат. Как это произойдёт? Смотрится, вот этот квадрат, который я нарисовал, он куда попадает? В бокс 2 или в бокс 3? Он попадает в бокс 2. Хорошо. Теперь этот квадрат куда попадает? Бокс 4, бокс 5. Он попадает в бокс 4. И я говорю: "О'кей, ты, значит, Бруклин Бриш, иди сходи". Либо если это визуализировать, это будет выглядеть вот так. Я ещё вот этот диапазон. И вот каждый раз я смотрю, о'кей, это в четвёртом, а это я потом бью на два. Где? В седьмом или в восьмом? О'кей, в седьмом. 13, 14, 15. О'кей, где 13 и в 14. Чуть-чуть, конечно, необычно на это перестроиться.

Значит, основная проблема в том, что как им пользоваться. Пользоваться вы с точки зрения пользователя вы, в принципе, просто его накинете, да, и у вас начнёт всё работать великолепно. Но как это строится? Это строится супер специфично, честно. Это строится суперспецифично. Давайте я перезагружу страничку. Что-то с ней не то стало. Строится супер специфично. Значит, R3 строится таким образом, что мы стараемся Так, где этот йпер? Ага, вот R3. Вот тут есть правило, как построить R3. Если кому-то интересно, можете посмотреть, можете попробовать реализовать. Здесь прямо пошагово каждый раз, что делать, как инициализировать, как с чем проверять, как там искать, как строить пересечение. Вот. Но мы, по сути, стараемся минимизировать вот эту метрику. То есть когда мы добавляем новую ноду, что мы стараемся делать? Мы стараемся минимизировать площадь вот этой коробки, которая покроет эти ноды. И при этом стараемся ещё, чтобы она минимально пересекалась с другими коробками, да? То есть, например, вот сейчас смотрим, у нас сейчас одна коробка. Я добавляю ещё точку. ещё точку. Построилось две коробки. Теперь R0 R1 R2 теперь, когда я добавлю вот сюда точку, оно будет мерить. А что лучше с ней сделать? Её лучше при прибить к этой коробке или к этой коробке? Какая минимизирует площадь? Если никакая анимизирует площадь, он попробует: "А может быть, тогда из этих двух мне новую коробку составить?" Тогда, может, лучше будет, а здесь новую коробку оттечь, либо верхнюю коробку разбить, потому что ещё помним, что это работает как B3. Оно ещё старается его балансить, чтобы типа всё было равномерно по дереву раскидано, чтобы мы получили свою асимптотику поиска. И теперь вот я добавляю сюда точку, она к этому дереву. Добавляю сюда точку, к этой коробке, добавляю сюда точку, разбилась на три коробки. Добавляю сюда точку к этой коробке, к этой коробке, разбилась ещё на коробки. То есть он старается поддерживать высоту дерева и при этом минимизировать вот эту площадь покрытия. Вот супер специфичная структура данных, потому что она построена на геометрии. Я много скидывал в Telegram-канал блокпостов интересных, где это может применяться. Это применяется даже в геймдеве, где вы смотрите там, что какую часть вам сейчас надо отрендерить, что вам нужно показать. Плюс оно применяется в нрных пространствах, как я до этого говорил. То есть это можно посмотреть на Википедии, что это не обязательно вот такая двумер двумерная плоскость, что это может быть ещё и трёхмерное пространство, и там вы кубы вы такие строите. Вот. Ну, в общем, супер необычная структура данных. Про неё написаны целые книги. Плюс ещё есть различные вариации R3, R +3, R звёздочка 3. Вот. Но думаю, для собеседования вам этого будет достаточно.

Хорошо. Хорошо. Значит, смотрите, мы с вами посмотрели на сторж, посмотрели на индексы. Мы вообще много на что с вами уже успели посмотреть, да? То есть, если мы смотрим вот эту картинку, то мы на вот это посмотрели, да? Там мы на вот это чуть-чуть посмотрели. Что нам осталось? Нам осталось вот этот большой кусок, вот эти большие куски, вот эти большие куски. Но, но, но, но, но помните, в самом начале в презентации мы смотрели и вот здесь часто мелькалам. Вот тут построено на LSM. Вот здесь это построено на LSM. Если вы возьмёте, например, самый популярный сторож LSM какой-нибудь Rox DB, вы увидите, что много чего построено на LSM. Много чего построено на LSM, да? Что имеется в виду? Например, вы открываете CROCH, находите вот здесь storage модель. Вот. И оно построено на Kvalue на LSM. Хм. Div from Rox DB. А что такое LSM? LSM - это вообще другой подход к стореджу. Вообще другой подход к стореджу. Значит, какая у меня была проблема с деревом с B +3, что когда мы добавляли, мне приходилось иногда лочить и перестраивать дерево. Так, перестраивать дерево, ребалансировать, перестраивать, ребалансировать, сплитить. Вот LSM как бы призвана решить эту проблему и поддерживать вхвиad. Как она это делает? Как она это делает? Давайте я сейчас открою текстовый редактор. Ага. И давайте посмотрим на Rocksdb. Ага. Значит, это их официальный репозиторий. Facebook RDB storage engine server work storage focus fast storage. Хорошо, хорошо, хорошо, хорошо. Так и смотрим на вот эту структуру. Как это устроено? Как это устроено? Значит, это устроено довольно специфично. Довольно специфично, когда у нас идут записи. Когда у нас идут записи, записи добавляются в MМ Table. Как только MМ переполняется, оно скидывается вниз в SST файл. Потом эти СT файлы друг с другом компакт subджатся, да? Строится новый слой СТ файлов. Они компакт subмертся. Новый слой СТ файлов, новый слой SST файлов. При этом мы ведём в WR head log. И у нас есть какой-то манифест log. Тут пока ничего непонятно. Тут пока ничего непонятно. Но вот что имеется в виду. Вот что имеется в виду. Допустим, мы сейчас возьмём, что мы в памяти будем хранить структуру данных, которая называется. Мы называем mem table, но это структура данных. Это может быть красно-чёрное дерево, может бытьлист, может быть тот же самый наш B3, который мы видели. Хорошо. И у нас есть на диске уже конкретно наши уровни. И мы увидим вот что происходит у нас. Вот что у нас происходит. Смотрите, когда мы добавляем новую запись, значит, это квсто, то есть хранить ключ значения, но вас это не должно в заблуждение вводить. Вы можете хранить, например, ключ какой-нибудь прай один, а значение - это может быть там закодированный вообще весь тупол, вся запись. Значит, вы добавляете первичные значения. Значит, m table её одно свойство, что оно держит их отсортированными. Это структура данных, которая нам держит данные отсортированными. Order set. При этом каждый из вот этих SST, это sorted string table. Он тоже их держит отсортированными. Мы сейчас увидим, зачем нам это нужно. Давайте добавлять A2, а, B3, C4, D5, Е6. Хорошо, мы добавили пять записей. Здесь места нет. Что мы делаем? Мы берём их, флюшим на диск. Флюшим на диск. О'кей. Теперь здесь опять есть место. Давайте сделаем что-нибудь интереснее. Типа там А теперь стало три, а C стало deleted и H стало 5. Hi, J стало 3 и M стало 2. Опять переполнилось. Её мы тоже флюшим на диск. И тут уже поднялась типа там. Теперь мы опять можем писать здесь опять свободно. Значит, фишка в том, фишка в том, почему мы хорошо поддерживаем WR heavy workload здесь, потому что мы пишем сразу в m table. Как только она переполнитсь, мы её скидываем на диск, опять пишем table. Как только она переполнитсь, скидывали на диск, опять пишем able. То есть никакой вот здесь там перебалансировки, там ещё что-нибудь не происходит. Мы пишем, пишем, пишем. Раз скинули. Пишем, пишем, пишем. Разкинули, пишем, пишем, пишем. Раз скинули. Теперь, что у нас происходит в этот момент на диске, да? То есть то, что записи у нас классные стали, это мы с вами поняли. А что у нас с чтением? Что у нас с чтением? Вот это проблема. Допустим, у меня бы ещё добавилось здесь А10, B13. Да? Теперь, если кто-то бы пришёл и сказал: "Я хочу прочитать А". Мы бы сначала проверили в мемблее данные, мы бы сказали: "А10, всё, уходи". Хорошо. Но если кто-то придёт за D или кто-то придёт за C, что ему отдать? Тогда придётся идти на диск. О'кей, уже пунктик мы с вами запомнили. А на диске у нас условно, да, несколько таких файлов. А ещё есть какие-то уровни. Зачем нам эти уровни? Смотрите, здесь мы ставим тоже ограничение. Здесь мы ставим, например, что мы поддерживаем только там, э, не знаю, два файла определённой длины. Когда они заполнились, что нам нужно сделать? Нам нужно их смерть, скомпактить и слить на уровень ниже. Благодаря тому, что они отсортированные, мержити и компактить нам их гораздо легче. То есть вы можете увидеть такую задачу, например, на лидкоде, да, merka sorted linked list или там merch sorted, как это сделать правильно? То есть от того, что они отсортированы, нам это сделать гораздо проще. Даже если их там у нас может быть несколько этих тата табличек, к табличек, нам всё равно это сделать проще, да? То есть мы используем какую-нибуд там минхипу, либо когда их две, ставим там два указателя, просто выбираем, какой из них меньше. Один двигаем, другой не двигаем. Это специфика, можете посмотреть где-нибудь, либо у меня там на курс по алгоритму. Теперь нам нужно их слить вместе. Как мы их будем сливать? У каждой этой записи есть таймстп, когда она добавилась. Мы смотрим в одной А2, в одной А3. Какая свежее? Свежее А3. Значит, сюда пойдёт А3. У одной B3, у другой B вообще нету. Пойдёт B3. У одной C4, у другой C удалено вообще. Значит, какое пойдёт? C вообще сюда не прорастёт теперь. У одной D5, у другой D вообще нет. У одной E6 нету. И вот это сюда вот так пойдёт. Хорошо. Отсюда что мы ещё видим? Отсюда мы видим, что они растут от уровня к уровню. То есть здесь уже SST файл условно больше размером, да? Потом понятно, это отсюда можно удалять, это можно удалять, добавится ещё, они заполнятся, мы их сольём вот сюда вниз, появится здесь второй файл, да, тут тоже какое-то ограничение на уровень, когда его нужно сливать. Мы их сольём, скинем на уровень ниже, скинем на уровень ниже. Скинем на уровне ниже. Хорошо. При этом все файлы у нас иммутабельные. Что это значит? Вот мы их слили, да, мы их никак на месте не модифицируем. То есть там, когда что-то обновляется, удаляется, мы ничего не делаем. Мы их слили друг с другом на нижний уровень. Эти файлы можно, например, всё сносить. Либо, либо, либо, как вот делает неон, про который мы в начале лекции с вами поговорили, что благодаря тому, что они иммутабельные, мы их можем где-то у себя как-то архивировать, какую-то историю хранить, и мы можем конкретно как снапшоту, к определённой точке, как к определённым ССТ файлам, вот так бам и вернуться. То есть вы можете как-то их версионировать и потом с одного в другое конкретно возвращаться, вот где вы сейчас находитесь. То есть LSM log oriented storage, да, LSM storage - это вообще другой подход, как вы храните данные. То есть вы их не храните так, как мы в начале обсуждали, с пейджами, да, или ещё с чем-нибудь. Нет, вы храните их в мембле, потом скидываете на диск. У ССТ файлов тоже своя структура, у них там есть там свой формат, свой заголовок, но пока что примерно можете представить, что это просто ключ значения, ключ значения, ключ значения, ключ значения, ключ значения. Найс, найс, найс, найс, найс.

Значит, где у нас проблема? Проблема, что читать эти SST файлы дорого. Читать эти SST-файлы дорого. Например, когда я хочу найти А2, А2, что придётся делать? Придётся читать этот SST файл, да? Этот SST файл. Или тут, если их нет, придётся читать файл ниже, например, и там искать А2. Проблемка, проблемка, проблемка, проблемка. Понятно, можем это распараллелить, параллельно искать в этих файлах. Проблемка. Значит, какие для этого есть решения? Одно решение - это подход, который называется leveling. Значит, в одном подходе, что вы делаете? Вы в сT файле на нижних уровнях начинаете хранить рейджи. То есть, например, вы точно знаете, что вот этот файл - это реrange от A до C. Этот файл от D до E, нет, до F, до G, например. А когда они сольются, вот здесь, например, будет от A до G. О'кей. Это уже вам упрощает поиск. То есть вы теперь знаете, что если мой ключ в этом рендже, то он должен быть где-то в этих файлах. Другая оптимизация, это другой вариант, то есть это называется левелинг. Есть ещё тайринг - это когда вы не смотрите на это, не обращаете на это внимание на Kнжи, а сливаете вот как как есть, так и сливаете. Значит, чем один вариант лучше, чем другой. В одном вам нужно менеджить вот эти KNG, чтобы они сохранялись, а в другом вы сливаете, как вам далось. Хорошо, вроде KG чуть-чуть помогли, но есть ещё одна гениальная идея, которую мы можем увидеть вот здесь. Это использовать Bloomilльтр. Использовать Bloom фильтр. Значит, что такое? Что такое BLomфильтр? Что такое BLфильтр? Смотрите, у меня есть мы берём и делаем условно 20 битов, да, маску. Мы делаем 20 битов с вами маску и говорим, что вот у нас есть там, не знаю, пять хэш-функций. То есть получается у меня 100 битов. И теперь каждая хэш-функция мапит моё значение. Например, аа если у меня ke - это какой-нибудь там, не знаю, Влад, да, или что это может быть? Ну, давайте 10. Он говорит 10 мапится вот вот эти значения. Вот сюда, вот сюда, вот сюда, вот сюда. Теперь 13 мапится вот сюда, 15 мапится вот сюда. И теперь, значит, на этот файл, когда он строится файл, мы на него создаём вот такой bloom фильтр. На него создаём BL фильтр. И что мы благодаря ему можем сделать? Мы можем сразу сказать: "А здесь вообще есть семь?" И он нам скажет: "Се здесь нет". Почему? Потому что семь подсветят определённые биты, который в этой маске нет. А если бы это число семь здесь было, то этот бит бы подсветился точно, да? То есть, когда мы ищем 10, он нам подсветил биты, где есть 10. Но и теперь мы знаем, что 10 здесь, наверное, есть. Почему я говорю, наверное? Почему я говорю наверное? Потому что потому что в хэшфункции у вас могут быть коллизии. И что у вас может быть? У вас могут эту ячейку одну и ту же подсветить несколько значений, да? То есть самого 10, например, там нет. Самого 10 там, например, нет. Вот. О'кей. Не, вот смотрите, самого 13 здесь нет, но ячейки, где на которой мапится 13, подсвечены. Почему так произошло? Потому что просто пересечение нескольких значений замапилось в коэш функцию на эти же ячейки. И нам кажется по блумфильтру как будто оно там есть, но его на самом деле там нет. Его на самом деле там нет. То есть, то есть Blomфильтр нам вот что говорит. Если нам BLМФтер, то есть сейчас прозвучит как цитата из пацанского паблика. Если нам блумфильтр сказал, что есть, то там его может и не быть. Почему? Потому что просто у вас произошло пересечение. А, например, давайте ещё раз этот момент подсвечу, потому что он важен. Например, X у меня мапится в 01, да? G у меня мапится в 1 и Z у меня мапится в 1, нет, в 0 0 1 1. Вот до этого в BLМФILр мы добавили G и Z. Какой у меня получится бумфильтр? Он получится 1011. Придёт X со своим 1001, скажет, что там мои биты подсвечены. Ему скажут: "Да, братан, подсвечены твои биты". Но самого X там нет. Это просто G и Z дали такое пересечение, понимаете? И поэтому, если блумфильттер сказал, что есть, то там его может не быть. Но если Блумфильтер, если Блумфильттер сказал, что его там нет, то там точно нет. Там точно нет. Почему? Потому что если бы оно там было, его биты бы подсветились. Мы только зажигаем их. Но если они вообще не горят, да, то там ни пересечения, никак вообще там его нет. Найс. При этом, при этом мы помним, что каждый этот файл иммутабельный у нас. Каждый этот файл иммутабельный. Что это нам даёт? Это нам даёт то, что никогда из Блумфильтра никто удаляться не будет. Как мы его вот сюда повесили, он так у нас и будет висеть. Блумфильтр сам менять не надо, потому что если какое-то значение удалится, тогда появляются проблемы. Нам надо смотреть, а кто эти ячейки поджёг, типа мне их нужно теперь вычищать, мне их не нужно вычищать. вдруг они на другом пересечении нам попались. Но поскольку файлы мутабельные, теперь Bloomfieldр нам точно говорит, что может быть здесь есть, но когда нет, он то он точно говорит нет. И теперь, когда вы хотите найти определённый ключ, вы можете сходить в BLфильтр параллельно, и он вам скажет: "Слушай, вот эти файлы сказали, что может в них есть, иди посмотри". И ты идёшь, бам, и смотришь, и твой поиск ускорился. Пушка. Сказка. А вот здесь есть вот такой веб-сайт, который называется Compction. А у них ещё есть и доклад вроде на Ютбе есть, который можете посмотреть. Здесь различные виды того, когда мы решаем, а когда нам сливать вот эти таблички, там до какого размера их расти. Плюс эти параметры можно тюнить либо использовать другие стратегии того, как ты их компактишь. Да, при этом у вас могут быть стратегии, что там несколько уровней - это level, несколько уровней - это тар, да? То есть вот так разделено здесь. Ну там помните, да, что это пересекаешься, не пересекаешься RNG. Давайте посмотрим на ванилу. То есть, грубо говоря, LSM будет выглядеть вот так вот. Вы набиваете один файл, набиваете второй файл, набиваете третий файл, набираете четвёртый файл, бам, флюшнули их. Их их слили, флюшнули. Дальше набиваете ещё четыре флюшны. Набиваете ещё четыре флюшнули. Набиваете вот набиваете последний четвёртый. Теперь он смертся с добавится вот сюда. Они все смертся и добавятся на уровень ниже. Флюшнули, добавили. Флюшнули. Смерли. Смерли. Смерли, смерли. Смерли. Смерли. Смерли. Смерли. Смерли. Смерли. При этом вот здесь можно смотреть, например, а как нам различные стратегии того, когда мы когда мы компактим и там как мы менеджем наши ренжи, какой нам даст перформанance там в плане потребления, в плане IO, там как часто мы будем на диск ходить. Вот. Супер интересно поиграться. Советую просто открыть, посмотреть, доклады посмотреть. То есть здесь можно менять потом параметры. Как вы видите, здесь есть интересные параметры типа буфер и есть page sizй. Entry size. Так, page size. Что имеется в виду page size? Я вроде говорил, никакого нет здесь slotted pages. И вот как мы до этого увидели, slotted pages здесь нет. Но, но, но каждый SST файл, каждый сам вот этот SST файл бьётся на логические блоки PG. Вот. И потом там есть блок кэш, который тоже их умеет затягивать типа в память. Фух. Вопрос возникает, когда мы пишем Mem ttable, у нас может выключиться электричество. Что делать? Что эти данные пропали? Нет, эти данные не пропали, потому что мы делаем write ahead. То есть перед тем, как писать мем таблицу, мы пишем WR headlog и говорим: "Вот такие вот

такие изменения делаю. Вот такие вот такие ключе добавляю. Такие вот такие ключи добавляю".

Плюс у нас есть манифест log, который вообще трекает, что там, какое состояние, у каких SST файлов. Что мы не посмотрели, мы примерно представляем, как выглядят SST файлы, примерно понимаем, как выглядит merge. Мы не понимаем, что это такое, что за table. А давайте посмотрим, что нам на это говорит Roxdb. Что нам на это говорит Roxdb? А давайте я напишу вот сюда skip lister alert. И мы смотрим default implementation of table robblist skip list sorted set. Найс.

При этом, если мы пойдём на Википедию, мы увидим, что этот скиплист используется в дискорде. Хмм, интереснее ещё стало. Зачем в дискорде скиплист? Что за скиплист такой? Значит, приготовьтесь, потому что skipлист - это супер необычная структура данных. Представим, у нас есть обычный linked list. Я в него добавляю один, я в него добавляю два. Я в него добавляю 10. Я в него добавляю 11. О'кей, всё понятно. Теперь, чтобы добавить там семь, нужно будет дойти до туда, где надо добавить семь. Там бамбамба, сюда вставить. О'кей, хорошо. Пока порядок держит сортировано, но какие-то, конечно, вставки дорогие, да, поиск получается линейный, поэтому придумали вот такую хитрую оптимизацию, которая называется skipлист.

Значит, skipлист - это вероятностная структура данных, которая нам даёт сложность log и использует подход, похожий, как работает Binary Search Tree. Смотрите, я сюда добавлю пять и вот сюда поставлю параметр 1. Этот параметр здесь я задаю руками в учебных целях, но вообще он выбирается рандомно. И смотрите, что он сделает. Ты что вообще? Это что такое было? Он прорастил значение пятёрки наверх на несколько этажей. Да, тут, к сожалению, сейчас этажи пересеклись. Ой, что я сделал? Ах, как жалко. Ну, давайте ещё поднаправляем. Как жаль, как жаль, как жаль. Да. И давайте, я бы хотел, чтобы у меня, например, семь вот здесь не был, а семь у меня прямо хорошо пророс. Во, неплохо. Значит, каждый раз, когда добавляется значение, оно ещё прорастает наверх на несколько этажей. И вот этот момент, на сколько этажей она прорастёт наверх, сдаётся нам рандомно. Но что нам теперь это даёт? Теперь, когда я хочу вставить, например, де сделать? Я иду по верхнему этажу и смотрю, а девять где? Вот я дошёл до семи. Я такой: "О'кей, 9 больше семи, значит, это в правой части вот этого linked list'а". Оно меньше 12, значит, оно где-то между 7 и 12. Я отсюда опускаюсь вниз. Теперь есть ссылка вниз, на следующий этаж. Я смотрю, а де больше семи, больше, а больше восьми, больше. О'кей. Значит, оно где-то вот здесь уже находится. Опускаясь отсюда вниз и вставляю нашу девятку. И благодаря рандому у нас посчитано так, что у нас ноды будут прорастать наверх, да, и они прорастут таким образом, что в среднем мы получаем log n. В среднем мы получаем log n. То есть он у нас так разрядится, что смотрите, получается логика такая же, как у нас в Binary Search Tree. То есть это как указатели. Мы такие: "О'кей, больше семи, меньше семи. Если больше, то мы точно знаем, что во второй половине этого linked list'а там справа надо проверять". При этом можем опуститься вниз, там будут какие-то новые, например, указатели. Мы по ним можем понять. А вот здесь уже будет храниться там наши значения key-value, которые мы возьмём, они у нас в отсортированном виде. Бам! Флюшнем на диск. Пушка. Супер необычная структура данных. Я понимаю, супер необычная структура данных, но что есть, то есть. Что есть, то есть. Есть, э, задача на лидкоде Skip list. Есть задача на литкоде. Дизайн Skip list. Я вам рекомендую её порешать. Рекомендую её порешать. вообще просто для себя разобраться со скиплистом, что здесь происходит. Вот очень необычная структура данных, супер интересная, да, шанс, что вы ещё где-то её встретите, конечно, маловат, но для себя разобраться будет прикольно.

Хорошо. Значит, мы посмотрели с вами ещё и на альтернативный подход, как можно менеджить свой storage, это LSM Storage. То есть сейчас уже не так очевидно, потому что у нас есть вот эти вариации B-tree с буферами, да, но примерно на вот этой на вот этом примерно вы должны почувствовать, почему для там heavy, WR intensive или почему для распределения вы используете LSM storage. Во-первых, вам у вас тут типа key-value значения. Вы можете ренджи легче дробить или легче это там куда-нибудь зашардировать. Потом, э, вы на запись не тратите время, вы просто флюшите. Это у вас там внизу компакт происходит. При этом на чтение, конечно, вы теряете. Вот RocksDB реализация LSM Stage, который мне где используется. При этом я опять же вам рекомендую вернуться к тому репозиторию, про который я уже часто говорил. Talentplan. Talentplan. А таки kv, где вы будете строить свой storage поверх ээ lsm storage. Там не использовать badger. Вот посмотрите, посмотрите. Правда, будет интересно.

Хорошо. Значит, в картине мира мы разобрались с вот этим, разобрались с вот этим. Нам осталось вот это и вот это. Вот это тема двух будущих лекций. А с вот этим можно, в принципе, и разобраться сейчас. Смотрите. Но вот это люди карьеры и научные труды тратят, да, вот это миллионы долларов. Потому что если вы делаете вот это хорошо, то, ну, у вас получаете перфоманс бур-бур, и это миллионы долларов. К сожалению, я вам не смогу сейчас рассказать на миллион долларов, но расскажу, расскажу, как знаю.

Значит, смотрите, когда к вам приходит запрос, да, вы пишете свой стандартный SQL, там select from, бла-бла-бла-бла-бла-бла-бла, бла-бла-бла-бла-бла. А, да, вам не видно слайд. Здесь написано статистика о данных. Статистика о данных. Значит, select from blint bl. Вот вот пришёл вам запрос. Сначала он попадает в parser-сертатор. Что происходит? Он просто как условно когда вы пишете свой программистский код, да, он у вас парсится и проверяется вообще валидна эта конструкция. Ну, то есть этот код в принципе валиден. То, что вы написали, это валидный SQL или невалидный SQL. После того, как он поймёт, что это валидный SQL, он построит из вашего запроса выражение реляционной алгебры. Что имеется в виду? Имеются в виду вот такие вот э каракули, да? Сейчас мы их разберём. После этого он построит вам несколько эквивалентных выражений, пойдёт в статистику о данных, там где, в какой реляции, сколько туплов, там, ээ, где какой индекс навешен, там насколько это прогрето, насколько это не прогрето. В общем, максимально о ваших данных соберёт соберёт информации, пропустит через оптимизаторы, выберет план, который для вас будет самый оптимальный. Потом этот план выполнится на ваших данных, и вы получите, соответственно, свой результат, да? То есть план, например, вашего запроса вы можете посмотреть через Explain Analyze. Через Explain Analyse, потом вставить какой-нибудь вот такой веб-сайт, и он вам нарисует, что с вашим планом. И, например, там, что было самое дорогое в вашем плане, где там дольше всего, больше I операции. Тут вы увидите, что, например, секскан, и, может быть, вы поймёте, что на этот запрос может попробовать какой-нибудь индекс накинуть, чтобы не делать сексскан, да, или там как-то прогреть по-другому за запрос перестроить. Вот. Но оптимизатор запросов попытается оптимизировать за вас и построить запрос оптимальным образом.

Например, смотрите, вот вот этот момент, когда он строит выражение реляционной алгебры. Вот каждый вот этот значок, он что-то значит. Он что-то значит. Спасибо, капитан. Очевидности. Каждый этот значок что-то значит. Золотые цитаты Влате, запишите. Значит, вот этот значок, да, это проекция. Что это значит? Это значит курс ID title и курс. Если переводить на SQL, это select курс курс ID title from. Вот так вот то, что мы выбираем курс ID title. Вот этот значок - это join teaches. Вот этот значок - это joins instructor. Вот этот значок de name равно music. Это типа select по условию. То есть выглядит select звёздочка from откуда? Ну вот от из этого выражения, которое у вас получилось вере ver вере. Вот name равно music where deep name равно music. Вот вот это where. Вот это вот вот этот значок. Вот этот значок. Хорошо. Что мы отсюда понимаем? Значит, у нас выгребаются все курсы. Они джойнтся, стичатся, чтобы посмотреть, там какая-то, скорее всего, маппинг таблица, где мы смотрим, какой преподаватель что преподаёт, какой курс. Мы мапим, джойним с ним, потом джойним с преподавателями, и нам нужны только преподаватели, которые в департаменте музыки работают. Значит, оптимизатор смотрит на это выражение не такое. А зачем мне джойнить со всеми преподавателями, если я могу заджойнить только с теми, кто преподаёт музыку, потому что я их всё равно там сверху их отфильтрую? Давай я сразу отфильтрую тех, кто работает в музыке, а потом начну джойнить. И вот эти, например, операции я могу сделать теперь параллельно. Он перестраивает этот запрос, перестраивает это дерево и получает там и выдаёт вам оптимальный запрос. Как он понял, что я могу безболезненно вот это вот сюда типа опустить, и всё будет нормально, да? Там вот этот оператор опустить вниз. Но он не просто так это понял, потому что у нас есть законы, по которым в реляционной алгебре можем выражение типа перетаскивать, да? У нас есть закон эквивалентности, например, например, смотрите, вот это селект по одному условию и по второму условию из таблички то же самое, что селект по одному вложенный в селект по-другому. То есть, если это переводить, а в SQL, если это переводить в SQL, то это будет выглядеть вот так, типа вы делали select, а звёздочка from select звёздочка from where condition 1 where condition 2. Это то же самое. То же самое, что я сделал бы вот так. Select звёздочка from X condition 1 and condition 2. То есть вот это то же самое, что вот это. Я могу вот это превратить в вот это, например. Или от того, что я вот здесь condition 1, condition 2 поменяю местами, тоже ничего не изменится, да? Это уже закон коммутативности. Вот, вот это здесь написано. Вот condition 1 и 2 то же самое, что вот эта вложенность или то же самое, что я их местами поменяю. Следующий закон. Когда я делаю join по какому-то условию, это то же самое вот этот join и вот этот join. Если мы джойним вот это потом с вот этим, это то же самое, что джойнить вот это с вот этим. Либо вот то, что используется как раз-таки в нашем примере. Если я джойню, а потом фильтрую по какому-то условию, это то же самое, что сначала отфильтрую по условию, а потом заджойню. Либо вот это, вот это декартовое произведение. Это все попарно комбинации. Взять все попарно комбинации, а потом из них выбрать по условию то же самое, что заджойнить по условию. Или вот здесь заджойнить по условию два, а потом выбрать по условию один - это то же самое, что заджойнить сразу по условию 1 и 2. И вот с помощью вот таких операторов, с помощью вот таких операторов, с помощью вот таких законов, да, там, ну, можете почитать в книге Паруса, здесь их навал. С помощью вот таких законов и операторов мы можем превращать одно дерево выражения в другое дерево выражение, в эквивалентное, да? эквивалентная, то есть это значит, она несёт там такой же смысл, да? Мы ничего не потеряли, мы саму логику запроса не поменяли. Мы поменяли дерево выражения, но как бы смысл запроса он не изменился, да? Мы не сделали так, что ты там хотел фильтровать по музыке, а теперь ты не фильтруешь по музыке. Нет, мы всё сохранили, просто перестроили так, чтобы было оптимальнее.

[музыка]

На этом эта лекция закончена. Спасибо вам большое. Сердечно благодарен, что вы со мной посидели, меня послушали. Значит, вот этот компонент и вот этот компонент мы обсудим на следующих лекциях. Будут вопросы, пожалуйста, пишите комментарии. А что-то где-то вам не понравилось, что-то где-то вы там увидели, пожалуйста, мне обязательно об этом сообщите. Но ещё раз, дисклеймер, это всё делается в учебном формате, как бы мы как будто каждый раз что-то изобретаем. Вот. Спасибо большое. Спасибо, спасибо за внимание, правда. Ценю, ценю вас. Удачи. Пока. Ну всё, чал, не могу говорить пока. Домашка в описании.