<!DOCTYPE html>
<html class="h-100" data-bs-theme="light" data-mantine-color-scheme="light" lang="ru" prefix="og: https://ogp.me/ns#">
<head>
<meta content="width=device-width, initial-scale=1.0" name="viewport">
<meta content="IE=Edge" http-equiv="X-UA-Compatible">
<link crossorigin="true" href="https://cdn.hexlet.io" rel="preconnect">
<link href="https://mc.yandex.ru" rel="preconnect">
<meta content="aa2vrdtq64dub8knuf83lwywit311w" name="facebook-domain-verification">
<link href="/favicon.ico" rel="icon" sizes="any">
<link href="/favicon.svg" rel="icon" type="image/svg+xml">
<link href="/apple-touch-icon.png" rel="apple-touch-icon">
<link href="/manifest.webmanifest" rel="manifest">
<script>
//<![CDATA[
window.gon={};gon.ym_counter="25559621";gon.is_bot=true;gon.applications={};gon.current_user={"id":null,"last_viewed_notification_id":null,"email":null,"state":null,"first_name":"","last_name":"","created_at":"2026-02-26 23:16:16 UTC","current_program":null,"current_team":null,"full_name":"","guest":true,"can_use_paid_features":false,"is_hexlet_employee":false,"sanitized_phone_number":"","can_subscribe":true,"can_renew_education":false};gon.token="XkY3z2WD1I5Md9jcZ43meE6xFLRvhhxHvEZUmdUULEKxl_z4l_157vo0_ERrghYPjrg5Hmex4uUBps7NhxPLLA";gon.locale="ru";gon.language="ru";gon.theme="light";gon.rails_env="production";gon.mobile=false;gon.google={"analytics_key":"UA-1360700-51","optimize_key":"GTM-5QDVFPF"};gon.captcha={"google_v3_site_key":"6LenGbgZAAAAAM7HbrDbn5JlizCSzPcS767c9vaY","yandex_site_key":"ysc1_Vyob5ZPPUdPBsu0ykt8bVFdzsfpoVjQChLGl2b4g19647a89","verification_failed":null};gon.social_signin=false;gon.typoreporter_google_form_id="1FAIpQLSeibfGq-KvWQ2Fyru-zkFFRVTLBuzXAHAoEyN1p49FtDmNoNA";
//]]>
</script>
<meta charset="utf-8">
<title>B-деревья | Алгоритмы на деревьях</title>
<meta name="description" content="B-деревья / Алгоритмы на деревьях: Познакомимся с B-деревьями и особенностями реализации операций с ними">
<link rel="canonical" href="https://ru.hexlet.io/courses/algorithms-trees/lessons/btrees/theory_unit">
<meta name="robots" content="noarchive">
<meta property="og:title" content="B-деревья">
<meta property="og:title" content="Алгоритмы на деревьях">
<meta property="og:description" content="B-деревья / Алгоритмы на деревьях: Познакомимся с B-деревьями и особенностями реализации операций с ними">
<meta property="og:url" content="https://ru.hexlet.io/courses/algorithms-trees/lessons/btrees/theory_unit">
<meta name="csrf-param" content="authenticity_token" />
<meta name="csrf-token" content="V4lQ850wS0ewJE4h-vx_qcKGVZHU4qi1oJP_hfn9cYu4WJvEb07mJwZnarn284_eAo94O9zVVhcdc2XRq_qW5Q" />
<script src="/vite/assets/inertia-DfXos102.js" crossorigin="anonymous" type="module"></script><link rel="modulepreload" href="/vite/assets/chunk-DsPFFUou.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/preload-helper-BJ4cLWpC.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/init-BrRXra1y.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/ahoy-DrlRQ-1D.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/analytics-cb8xch9l.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/ErrorFallbackBlock-naDSYSy9.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Surface-DL2bpZA-.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/gon-D3e4yh1x.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/mantine-CGMYrt2Y.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/utils-DRqSHbQE.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/routes-CCH8ilKF.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/extends-C-EagtpE.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/inheritsLoose-BBd-DCVI.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/objectWithoutPropertiesLoose-DRHXDhjp.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/index.esm-DAqKOkZ0.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Button-CGPUux8l.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/CloseButton-D1euiPao.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Group-BX48WcuU.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Loader-BQEY8g6v.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Modal-Cy3HByv7.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/OptionalPortal-1Hza5P2w.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Stack-CtjJzfw4.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Textarea-Ck64llAy.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Box-B5-OOzBf.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/DirectionProvider-Dc9zdUke.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/events-DJQOhap0.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/use-reduced-motion-D2owz4wa.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/use-disclosure-zKtK5W1r.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/use-hotkeys-Cnc_Rwkb.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/random-id-DOQyszCZ.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/notifications.store-C-3AFSMn.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/exports-C_MrNx_T.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/axios-BEvgo0ym.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/dayjs.min-BkKovM-s.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/i18next-BlSq9s7B.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/client-U9M77rxp.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/react-dom-DaLxUz_h.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/useTranslation-Bx1Cdrkz.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/compiler-runtime-6XxiPFnt.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/jsx-runtime-CwjcCKJi.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/react-CkL4ZRHB.js" as="script" crossorigin="anonymous">
<link rel="stylesheet" href="/vite/assets/application-BqhCP46M.js" />
<script src="/vite/assets/application-Df9RExpe.js" crossorigin="anonymous" type="module"></script><link rel="modulepreload" href="/vite/assets/chunk-DsPFFUou.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/autocomplete-VMNbxKGl.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/routes-CCH8ilKF.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/createPopper-C3aM9r1M.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/js.cookie-D1-O8zkX.js" as="script" crossorigin="anonymous"><link rel="stylesheet" href="/vite/assets/application-C8HjmMaq.css" media="screen" />
<script>
window.ym = function(){(ym.a=ym.a||[]).push(arguments)};
window.addEventListener('load', function() {
setTimeout(function() {
ym.l = 1*new Date();
ym(window.gon.ym_counter, "init", {
clickmap: true,
trackLinks: true,
accurateTrackBounce: true,
webvisor: true
});
// Загружаем скрипт
var k = document.createElement('script');
k.async = 1;
k.src = 'https://mc.yandex.ru/metrika/tag.js';
document.head.appendChild(k);
ym(window.gon.ym_counter, 'getClientID', function(clientID) {
window.ymClientId = clientID;
});
}, 1500);
});
</script>
<!-- Google Tag Manager - deferred -->
<script>
// dataLayer stub сразу — пуши работают до загрузки скрипта
window.dataLayer = window.dataLayer || [];
// Сам скрипт — отложенно после load
window.addEventListener('load', function() {
setTimeout(function() {
dataLayer.push({'gtm.start': new Date().getTime(), event: 'gtm.js'});
var j = document.createElement('script');
j.async = true;
j.src = 'https://www.googletagmanager.com/gtm.js?id=GTM-WK88TH';
document.head.appendChild(j);
}, 1500);
});
</script>
<!-- End Google Tag Manager -->
</head>
<body>
<noscript>
<div>
<img alt="" src="https://mc.yandex.ru/watch/25559621" style="position:absolute; left:-9999px;">
</div>
</noscript>
<header class="sticky-top bg-body">
<nav class="navbar navbar-expand-lg">
<div class="container-xxl">
<a class="navbar-brand" href="/"><img alt="Логотип Хекслета" height="24" src="https://ru.hexlet.io/vite/assets/logo_ru_light-BpiEA1LT.svg" width="96">
</a><button aria-controls="collapsable" aria-expanded="false" aria-label="Меню" class="navbar-toggler border-0 mb-0 mt-1" data-bs-target="#collapsable" data-bs-toggle="collapse">
<span class="navbar-toggler-icon"></span>
</button>
<div class="collapse navbar-collapse" id="collapsable">
<ul class="navbar-nav mb-lg-0 mt-lg-1">
<li class="nav-item dropdown">
<button aria-haspopup class="btn nav-link" data-bs-toggle="dropdown" type="button">
Все курсы
<span class="bi bi-chevron-down align-middle ms-1"></span>
</button>
<ul class="dropdown-menu">
<li>
<a class="dropdown-item d-flex py-2" href="/courses"><div class="fw-bold me-auto">Все что есть</div>
<div class="text-muted">117</div>
</a></li>
<li>
<hr class="dropdown-divider">
</li>
<li class="dropdown-item">
<b>Популярные категории</b>
</li>
<li>
<a class="dropdown-item py-2" href="/courses_devops">Курсы по DevOps
</a></li>
<li>
<a class="dropdown-item py-2" href="/courses_data_analytics">Курсы по аналитике данных
</a></li>
<li>
<a class="dropdown-item py-2" href="/courses_programming">Курсы по программированию
</a></li>
<li>
<a class="dropdown-item py-2" href="/courses_testing">Курсы по тестированию
</a></li>
<li>
<hr class="dropdown-divider">
</li>
<li class="dropdown-item">
<b>Популярные курсы</b>
</li>
<li>
<a class="dropdown-item py-2" href="/programs/devops-engineer-from-scratch">DevOps-инженер с нуля
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/go">Go-разработчик
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/java">Java-разработчик
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/python">Python-разработчик
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/qa-auto-engineer-java">Автоматизатор тестирования на Java
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/data-analytics">Аналитик данных
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/frontend">Фронтенд-разработчик
</a></li>
</ul>
</li>
<li class="nav-item dropdown">
<button aria-haspopup class="btn nav-link" data-bs-toggle="dropdown" type="button">
О Хекслете
<span class="bi bi-chevron-down align-middle"></span>
</button>
<ul class="dropdown-menu bg-body">
<li>
<a class="dropdown-item py-2" href="/pages/about">О нас
</a></li>
<li>
<a class="dropdown-item py-2" href="/blog">Блог
</a></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://special.hexlet.io/hse-research" role="button">Результаты (Исследование)
</span></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://career.hexlet.io" role="button">Хекслет Карьера
</span></li>
<li>
<a class="dropdown-item py-2" href="/testimonials">Отзывы студентов
</a></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://t.me/hexlet_help_bot" role="button">Поддержка (В ТГ)
</span></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://special.hexlet.io/referal-program/?promo_creative=priglasite-druzei&promo_name=referal-program&promo_position=promo_position&promo_start=010724&promo_type=link" role="button">Реферальная программа
</span></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://special.hexlet.io/certificate" role="button">Подарочные сертификаты
</span></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://hh.ru/employer/4307094" role="button">Вакансии
</span></li>
<li>
<span class="dropdown-item d-flex external-link" rel="noopener noreferrer nofollow" data-href="https://b2b.hexlet.io" data-target="_blank" role="button">Компаниям
</span></li>
<li>
<span class="dropdown-item d-flex external-link" rel="noopener noreferrer nofollow" data-href="https://hexly.ru/" data-target="_blank" role="button">Колледж
</span></li>
<li>
<span class="dropdown-item d-flex external-link" rel="noopener noreferrer nofollow" data-href="https://hexlyschool.ru/" data-target="_blank" role="button">Частная школа
</span></li>
</ul>
</li>
<li><a class="nav-link" href="/subscription/new">Подписка</a></li>
</ul>
<ul class="navbar-nav flex-lg-row align-items-lg-center gap-2 ms-auto">
<li>
<a class="nav-link" aria-label="Переключить тему" href="/theme/switch?new_theme=dark"><span aria-hidden="true" class="bi bi-moon"></span>
</a></li>
<li>
<span data-target="_self" class="nav-link external-link" data-href="/u/new" role="button"><span>Регистрация</span>
</span></li>
<li>
<span data-target="_self" class="nav-link external-link" data-href="https://ru.hexlet.io/session/new" role="button"><span>Вход</span>
</span></li>
</ul>
</div>
</div>
</nav>
</header>
<div class="x-container-xxxl">
</div>
<main class="mb-6 min-vh-100 h-100">
<link rel="preload" as="image" href="https://hexlet.io/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6NDAyOCwicHVyIjoiYmxvYl9pZCJ9fQ==--ae9eed98663dd1201759d042a5ba7ca790866156/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJ3ZWJwIiwicmVzaXplX3RvX2xpbWl0IjpbNDAwLDQwMF0sInNhdmVyIjp7InF1YWxpdHkiOjg1fX0sInB1ciI6InZhcmlhdGlvbiJ9fQ==--5b6f46dacd1af664f27558553a58076185091823/Programming-bro.png"/><link rel="preload" as="image" href="/vite/assets/development-BVihs_d5.png"/><div id="app" data-page="{"component":"web/courses/lessons/theory_unit","props":{"errors":{},"locale":"ru","language":"ru","httpsHost":"https://ru.hexlet.io","host":"ru.hexlet.io","colorScheme":"light","auth":{"user":{"id":null,"last_viewed_notification_id":null,"email":null,"state":null,"first_name":"","last_name":"","created_at":"2026-02-26T23:16:16.458Z","current_program":null,"current_team":null,"full_name":"","guest":true,"can_use_paid_features":false,"is_hexlet_employee":false,"sanitized_phone_number":"","can_subscribe":true,"can_renew_education":false}},"cloudflareTurnstileSiteKey":"0x4AAAAAAA15KmeFXzd2H0Xo","vkIdClientId":"51586979","yandexIdClientId":"88d071f1d3384eb4bd1deb37910235c7","formAuthToken":"1RryCAFeq3-wevAiVmMFbxLaJCcSTXWDjdYayE-_k0A6yzk_8yAGHwY51LpabPUY0tMJjRp6iyEwNoCcHbh0Lg","topics":[{"id":90693,"title":"```js\nclass BTreeNode {\n constructor(value, parent) {\n this.leaf = false; // Флаг, который показывает, что текущий узел является листовым\n this.keys = new Array(); // Массив ключей (полезной нагрузки) узла\n this.parent = parent; // Cсылка на родителя\n this.children = new Array(); // Массив дочерних узлов\n }\n}\n```\nvalue в конструкторе не используется","plain_title":"class BTreeNode { constructor(value, parent) { this.leaf = false; // Флаг, который показывает, что текущий узел является листовым this.keys = new Array(); // Массив ключей (полезной нагрузки) узла this.parent = parent; // Cсылка на родителя this.children = new Array(); // Массив дочерних узлов } } value в конструкторе не используется ","creator":{"public_name":"Ильдар","id":362775,"is_tutor":false},"comments":[{"creator":{"public_name":"Ivan Gagarinov","id":75907,"is_tutor":true},"id":179897,"body":"**Ильдар**, спасибо! Поправил!","topic_id":90693}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"B-деревья","entity_url":null,"active":true}},{"id":97001,"title":"Что-то изображение с примером В-дерева, где указаны ключи (корень `[233, 449]`) для меня не сходится с описанием свойств такого дерева. В частности, не сходится свойство\n\n> Нелистовой узел с k потомками имеет k-1 ключей\n\nВозьмем корневую ноду. У корня три потомка, т.е. k = 3. Тогда у самого корневого узла должно быть (3 - 1) = 2 ключа. Верно, ключи `233, 449`.\n\nДалее самый левый дочерний нелистовой узел. Три потомка, т.е. ключа тоже должно быть два. Но их 4. Почему?\n\nУ самого правого дочернего нелистового узла тоже три потомка. Но ключа тоже три.\n\nПодскажите, пожалуйста, это я что-то не так понимаю или иллюстрирующий пример неверный?\n\nИ ещё вопрос по коду узла В-дерева. Если у узла есть поле `this.keys`, которое подписано как \"массив полезной нагрузки\", то зачем там отдельно поле `this.value`, которое тоже вроде как полезная нагрузка?\nС моей точки зрения кажется, что они друг другу противоречат. Я бы понял, если бы на основе переданного в конструкторе `value` создавался бы начальный вариант массива ключей, т.е.\n```\nconstructor(value, parent) {\n ....\n this.keys = [value]; // Массив ключей (полезной нагрузки) узла\n ....\n }\n```\nи потом можно было бы дополнить `this.keys` новыми значениями. А тут и `this.keys` просто пустой массив при создании узла, и непонятно, для чего `this.value` нужен.","plain_title":"Что-то изображение с примером В-дерева, где указаны ключи (корень [233, 449]) для меня не сходится с описанием свойств такого дерева. В частности, не сходится свойство Нелистовой узел с k потомками имеет k-1 ключей Возьмем корневую ноду. У корня три потомка, т.е. k = 3. Тогда у самого корневого узла должно быть (3 - 1) = 2 ключа. Верно, ключи 233, 449. Далее самый левый дочерний нелистовой узел. Три потомка, т.е. ключа тоже должно быть два. Но их 4. Почему? У самого правого дочернего нелистового узла тоже три потомка. Но ключа тоже три. Подскажите, пожалуйста, это я что-то не так понимаю или иллюстрирующий пример неверный? И ещё вопрос по коду узла В-дерева. Если у узла есть поле this.keys, которое подписано как \"массив полезной нагрузки\", то зачем там отдельно поле this.value, которое тоже вроде как полезная нагрузка? С моей точки зрения кажется, что они друг другу противоречат. Я бы понял, если бы на основе переданного в конструкторе value создавался бы начальный вариант массива ключей, т.е. constructor(value, parent) { .... this.keys = [value]; // Массив ключей (полезной нагрузки) узла .... } и потом можно было бы дополнить this.keys новыми значениями. А тут и this.keys просто пустой массив при создании узла, и непонятно, для чего this.value нужен. ","creator":{"public_name":"Артём Абрамянц","id":125736,"is_tutor":false},"comments":[{"creator":{"public_name":"Maksim Litvinov","id":198906,"is_tutor":true},"id":188029,"body":"Приветствую, Артем! Спасибо, что обратили внимание. Действительно, как будто бы рисунок не совпадает с описанием. Оформил ваше замечание в тикет, разберемся","topic_id":97001}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"B-деревья","entity_url":null,"active":true}},{"id":95381,"title":"Почему в диапазоне от 30 до 50 есть числа 11, 17, 23?","plain_title":"Почему в диапазоне от 30 до 50 есть числа 11, 17, 23? ","creator":{"public_name":"Константин Клубков","id":449818,"is_tutor":false},"comments":[{"creator":{"public_name":"Maksim Litvinov","id":198906,"is_tutor":true},"id":186210,"body":"Приветствую, Константин! Да, вы правы, тут опечатка. Поправил, спасибо","topic_id":95381}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"B-деревья","entity_url":null,"active":true}},{"id":100626,"title":"Привет\n\n\"Нелистовой узел с k потомками имеет k - 1 ключей\" - в теории написано так, при этом рисунок выше имеет нелистовой узел с ключами [31, 97, 137, 191]. У этого узла 3 потомка, при этом узел имеет 4 ключа. Это ошибка в рисунке или я не так понял?","plain_title":"Привет \"Нелистовой узел с k потомками имеет k - 1 ключей\" - в теории написано так, при этом рисунок выше имеет нелистовой узел с ключами [31, 97, 137, 191]. У этого узла 3 потомка, при этом узел имеет 4 ключа. Это ошибка в рисунке или я не так понял? ","creator":{"public_name":"Dmitry Ким","id":697764,"is_tutor":false},"comments":[{"creator":{"public_name":"Olga Pejenkova","id":364375,"is_tutor":true},"id":192432,"body":"**Dmitry**, \n\nданное описание справедливо в целом для *B-деревьев*. Если применить его к рисунку выше, то теоретически есть еще два диапазона ключей для новых потомков: *(137-191)* и *(191-283)*. Итого получается, что максимально возможное число потоков у нелистового узла равно 5 (*k*), а сам узел имеет 4 ключа (*k-1*).","topic_id":100626}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"B-деревья","entity_url":null,"active":true}},{"id":100661,"title":"> Если в соседних узлах слишком мало ключей — занятость узлов падает ниже значения m/2\n\nПодскажите, что за внезапное определение занятости узлов и при чем здесь m/2, ранее в этой лекции было написано про m/2 в контексте минимального количества потомков, теперь речь про какую-то занятость","plain_title":"Если в соседних узлах слишком мало ключей — занятость узлов падает ниже значения m/2 Подскажите, что за внезапное определение занятости узлов и при чем здесь m/2, ранее в этой лекции было написано про m/2 в контексте минимального количества потомков, теперь речь про какую-то занятость ","creator":{"public_name":"Dmitry Ким","id":697764,"is_tutor":false},"comments":[{"creator":{"public_name":"Olga Pejenkova","id":364375,"is_tutor":true},"id":192441,"body":"**Dmitry**, \n\nЭто описание свойства В-дерева. Если *m* - это степень дерева, тогда \n\n* Каждый узел имеет не более *m* потомков\n* Каждый узел кроме корневого и листовых имеют не менее *m/2* потомков\n* ...\n\nДалее говорим об операциях, которые меняют стуктуру В-деревьев и о необходимости следить за сохранением свойств дерева. Например, при добавлении узел может переполняться, и тогда его надо разделять, или наоборот при удалении в узлах остается слишком мало ключей, и тогда узлы надо сливать. ","topic_id":100661}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"B-деревья","entity_url":null,"active":true}},{"id":100659,"title":"> Если при вставке превысилась максимальная степень узла, то узел нужно разделять на части.\n\nВ первом уроке максимальная степень узла имеет вообще другое определение:\n\n> Количество поддеревьев у узла называется его степенью. Максимальное значение степени узла — степень дерева. Если степень дерева равна двум, значит, у каждого узла может быть не более двух потомков:\n\nЗдесь речь, на сколько я понял, про заполненность массива, поэтом непонятно при чем здесь максимальная степень узла. Если говорить о джаве, то там вообще листы используются и таких проблем с переполнением массива не должно быть, поэтому сделали бы сноску хоть, что к джаве это не относится, а то время впустую потратил","plain_title":"Если при вставке превысилась максимальная степень узла, то узел нужно разделять на части. В первом уроке максимальная степень узла имеет вообще другое определение: Количество поддеревьев у узла называется его степенью. Максимальное значение степени узла — степень дерева. Если степень дерева равна двум, значит, у каждого узла может быть не более двух потомков: Здесь речь, на сколько я понял, про заполненность массива, поэтом непонятно при чем здесь максимальная степень узла. Если говорить о джаве, то там вообще листы используются и таких проблем с переполнением массива не должно быть, поэтому сделали бы сноску хоть, что к джаве это не относится, а то время впустую потратил ","creator":{"public_name":"Dmitry Ким","id":697764,"is_tutor":false},"comments":[{"creator":{"public_name":"Olga Pejenkova","id":364375,"is_tutor":true},"id":192435,"body":"**Dmitry**, \n\nИспользовать массив или какие-то иные структуры данных языка программирования - это скорее детали реализации. \nВ этом фрагменте теории фокус на то, что необходимо следить за заполненностью узлов, чтобы она не превышала степень дерева, и если такое происходит, то описаны способы разбиения заполненного узла. \n","topic_id":100659}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"B-деревья","entity_url":null,"active":true}},{"id":102228,"title":"- Третий дочерний узел содержит ключи [76, 88] и имеет три листовых дочерних узла с ключами [71, 73, 75], [77, 85], и [89, 97].\nНо ведь \n\nТак как дерево у нас имеет два ключа, то максимум может иметь 3 дочерних узла - что говорит о том, что степень дерева равна 3-м\nСледовательно:\n\nДля B-дерева степени 3:\n\n- Каждый узел может содержать от ⌈ 3/2 ⌉ - 1 = 0 до 3 - 1 = 2 ключей. ***от 0 до 2-х***\n- Каждый узел может иметь от ⌈ 3/2 ⌉ = **от 2 до 3 дочерних узлов**.\n\nтогда ваше дерево получается не соответствует b-дереву \n\n**### Вопрос:** что за структура дерева у вас в упражнении ?\n","plain_title":"Третий дочерний узел содержит ключи [76, 88] и имеет три листовых дочерних узла с ключами [71, 73, 75], [77, 85], и [89, 97]. Но ведь Так как дерево у нас имеет два ключа, то максимум может иметь 3 дочерних узла - что говорит о том, что степень дерева равна 3-м Следовательно: Для B-дерева степени 3: Каждый узел может содержать от ⌈ 3/2 ⌉ - 1 = 0 до 3 - 1 = 2 ключей. от 0 до 2-х Каждый узел может иметь от ⌈ 3/2 ⌉ = от 2 до 3 дочерних узлов. тогда ваше дерево получается не соответствует b-дереву ### Вопрос: что за структура дерева у вас в упражнении ? ","creator":{"public_name":"Алексей Олещенко","id":582226,"is_tutor":false},"comments":[{"creator":{"public_name":"Maksim Litvinov","id":198906,"is_tutor":true},"id":194395,"body":"Почему не соответствует? Все же вписывается в условия, которые вы привели. У него два ключа - 76, 88 и три потомка - [71, 73, 75], [77, 85], и [89, 97]","topic_id":102228},{"creator":{"public_name":"Алексей Олещенко","id":582226,"is_tutor":false},"id":194415,"body":"[71, 73, 75] - этот потомок не соответствует, так как в B - дереве со степенью 3, ключей в каждом потомке может быть от 0 до 2-х. Тут их 3 )\n\nможет я что-то не так понял ?\n","topic_id":102228},{"creator":{"public_name":"Maksim Litvinov","id":198906,"is_tutor":true},"id":194417,"body":"Так ведь речь о степени узла. У узла два ключа и три потомка. Так что все ок. ","topic_id":102228},{"creator":{"public_name":"Алексей Олещенко","id":582226,"is_tutor":false},"id":194423,"body":"**Maksim Litvinov**, Порядок определяет количество дочерних узлов, а как высчитать максимальное количество ключей в узле, так же как высчитать максимум количество ключей в листе ?\n\nЕсли порядок дерева равен 3-м. \nСколько ключей может находится в листовом узле ?\n","topic_id":102228},{"creator":{"public_name":"Maksim Litvinov","id":198906,"is_tutor":true},"id":194437,"body":"> Корень содержит от 1 до 2t-1 ключей. Любой другой узел содержит от t-1 до 2t-1 ключей. Листья не являются исключением из этого правила\n\nПолучается в листе может быть от 2 до 5 ключей","topic_id":102228}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"B-деревья","entity_url":null,"active":true}},{"id":107263,"title":"> Нелистовой узел с *k* потомками имеет *k* - 1 ключей\n\nПодскажите, почему B-дерево, представленное как пример, в уроке и упражнении не обладает этим свойством?","plain_title":"Нелистовой узел с k потомками имеет k - 1 ключей Подскажите, почему B-дерево, представленное как пример, в уроке и упражнении не обладает этим свойством? ","creator":{"public_name":"Andrey Frolov","id":940644,"is_tutor":false},"comments":[{"creator":{"public_name":"Nikolai Gagarinov","id":104929,"is_tutor":true},"id":200970,"body":"Добрый день.\n\nВозможно тут нужно дополнить пример в теории. ОБратную связь передам автору, чтобы дополнили примеры.","topic_id":107263}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"B-деревья","entity_url":null,"active":true}},{"id":107720,"title":"Добрый день. Решение учителя в практическом упражнении не универсально.\nОно верно работает только на данном конкретном B-дереве из тестов.\n\nПопробуйте запустить тот же код для B-дерева такого вида:\nroot node: [ 30, 70, 125 ]\nchildren: [ 1, 8, 12 ] [ 40, 50, 60 ] [ 80, 90, 100 ] [ 130, 150, 200 ]\n\nКод упадёт. Даже если внести правки, чтобы не падал - итоговый массив будет содержать неверный результат.","plain_title":"Добрый день. Решение учителя в практическом упражнении не универсально. Оно верно работает только на данном конкретном B-дереве из тестов. Попробуйте запустить тот же код для B-дерева такого вида: root node: [ 30, 70, 125 ] children: [ 1, 8, 12 ] [ 40, 50, 60 ] [ 80, 90, 100 ] [ 130, 150, 200 ] Код упадёт. Даже если внести правки, чтобы не падал - итоговый массив будет содержать неверный результат. ","creator":{"public_name":"Andrey Frolov","id":940644,"is_tutor":false},"comments":[{"creator":{"public_name":"Nikolai Gagarinov","id":104929,"is_tutor":true},"id":201838,"body":"Добрый день.\n\nСпасибо, передам авторам курса ОС","topic_id":107720}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"B-деревья","entity_url":null,"active":true}}],"lesson":{"exercise":{"id":2489,"slug":"algorithms_trees_btrees_exercise","name":null,"state":"active","kind":"exercise","language":"javascript","locale":"ru","has_web_view":false,"has_test_view":false,"reviewable":true,"readme":"В этом упражнении вам предстоит поработать с B-деревом. Нужно будет написать функцию, которая найдет в B-дереве все значения, находящиеся в заданном диапазоне\n\nДля примера возьмем В-дерево, рассмотренное в уроке. Найдем в нем все значения в диапазоне от 30 до 50\n\n\n\n```javascript\nfindValuesInRange(tree, 30, 50); // [31, 41, 47]\n```\n\n## solutions/solution.js\n\nРеализуйте функцию `findValuesInRange()`, которая принимает три параметра: дерево, верхнюю и нижнюю границу диапазона. Функция должна вернуть массив всех значений дерева, находящиеся в заданном диапазоне\n\n```javascript\nfindValuesInRange(tree, 30, 50); // [31, 41, 47]\n```\n\nДобавьте в файл импорт\n\n```javascript\nimport buildBTree from '../helpers/helpers.js';\n```\n\nи создайте в файле функцию со следующим кодом\n\n```javascript\nexport default (data, min, max) => findValuesInRange(buildBTree(data), min, max);\n```\n\nЭтот код необходим для проверки решения автоматическими тестами\n\n## solutions/solution.php\n\nУсловия такие же как для JavaScript\n\n```php\n<?php\n\nfindValuesInRange($items, 30, 50); // [31, 41, 47]\n```\n\nПодключите файл\n\n```php\nrequire_once(__DIR__ . '/../helpers/helpers.php');\n```\n\nи создайте в файле функцию со следующим кодом\n\n```php\nfunction solution($data, $min, $max) {\n return findValuesInRange(buildBTree($data), $min, $max);\n}\n```\n\nЭтот код необходим для проверки решения автоматическими тестами\n\n## solutions/solution.py\n\nРеализуйте функцию `find_values_in_range()`, остальные условия такие же, как для JavaScript\n\n```python\nfind_values_in_range(items, 30, 50)\n## [31, 41, 47]\n```\n\nДобавьте в файл импорты\n\n```python\nimport os\nimport sys\n\nsys.path.append(os.path.abspath('/usr/src/app/'))\n\nfrom helpers.helpers import buildBTree\n```\n\nи создайте в файле функцию со следующим кодом\n\n```javascript\ndef solution(items, min, max):\n btree = buildBTree(items)\n return find_values_in_range(btree, min, max)\n\n```\n\nЭтот код необходим для проверки решения автоматическими тестами\n\n## solutions/Solution.java\n\nВ файле определите пакет `solutions` и создайте в нем публичный класс `Solution`. В классе реализуйте публичный статический метод `findValuesInRange()`. Метод принимает три параметра: само В-дерево (объект класса `BTreeNode`), верхнюю и нижнюю границу диапазона в виде целых чисел. Метод должен вернуть список `List<Integer>` значений, которые укладываются в этот диапазон (включая границы)\n\n```java\nList<Integer> values = Solution.findValuesInRange(tree, 30, 50);\nSystem.out.println(values); // => [31, 41, 47]\n```\n\nДобавьте в класс метод со следующим кодом\n\n```java\npublic static List<Integer> run(java.util.Map<String, Object> data, int min, int max) {\n return helpers.Helper.run(data, min, max);\n}\n```\n\nЭтот код необходим для проверки решения автоматическими тестами\n\n### Алгоритм\n\n* Структуру дерева, которое будет использоваться при проверке вашего решения, можно посмотреть в директории *\\_\\_fixtures\\_\\_*\n","prepared_readme":"В этом упражнении вам предстоит поработать с B-деревом. Нужно будет написать функцию, которая найдет в B-дереве все значения, находящиеся в заданном диапазоне\n\nДля примера возьмем В-дерево, рассмотренное в уроке. Найдем в нем все значения в диапазоне от 30 до 50\n\n\n\n```javascript\nfindValuesInRange(tree, 30, 50); // [31, 41, 47]\n```\n\n## solutions/solution.js\n\nРеализуйте функцию `findValuesInRange()`, которая принимает три параметра: дерево, верхнюю и нижнюю границу диапазона. Функция должна вернуть массив всех значений дерева, находящиеся в заданном диапазоне\n\n```javascript\nfindValuesInRange(tree, 30, 50); // [31, 41, 47]\n```\n\nДобавьте в файл импорт\n\n```javascript\nimport buildBTree from '../helpers/helpers.js';\n```\n\nи создайте в файле функцию со следующим кодом\n\n```javascript\nexport default (data, min, max) => findValuesInRange(buildBTree(data), min, max);\n```\n\nЭтот код необходим для проверки решения автоматическими тестами\n\n## solutions/solution.php\n\nУсловия такие же как для JavaScript\n\n```php\n<?php\n\nfindValuesInRange($items, 30, 50); // [31, 41, 47]\n```\n\nПодключите файл\n\n```php\nrequire_once(__DIR__ . '/../helpers/helpers.php');\n```\n\nи создайте в файле функцию со следующим кодом\n\n```php\nfunction solution($data, $min, $max) {\n return findValuesInRange(buildBTree($data), $min, $max);\n}\n```\n\nЭтот код необходим для проверки решения автоматическими тестами\n\n## solutions/solution.py\n\nРеализуйте функцию `find_values_in_range()`, остальные условия такие же, как для JavaScript\n\n```python\nfind_values_in_range(items, 30, 50)\n## [31, 41, 47]\n```\n\nДобавьте в файл импорты\n\n```python\nimport os\nimport sys\n\nsys.path.append(os.path.abspath('/usr/src/app/'))\n\nfrom helpers.helpers import buildBTree\n```\n\nи создайте в файле функцию со следующим кодом\n\n```javascript\ndef solution(items, min, max):\n btree = buildBTree(items)\n return find_values_in_range(btree, min, max)\n\n```\n\nЭтот код необходим для проверки решения автоматическими тестами\n\n## solutions/Solution.java\n\nВ файле определите пакет `solutions` и создайте в нем публичный класс `Solution`. В классе реализуйте публичный статический метод `findValuesInRange()`. Метод принимает три параметра: само В-дерево (объект класса `BTreeNode`), верхнюю и нижнюю границу диапазона в виде целых чисел. Метод должен вернуть список `List<Integer>` значений, которые укладываются в этот диапазон (включая границы)\n\n```java\nList<Integer> values = Solution.findValuesInRange(tree, 30, 50);\nSystem.out.println(values); // => [31, 41, 47]\n```\n\nДобавьте в класс метод со следующим кодом\n\n```java\npublic static List<Integer> run(java.util.Map<String, Object> data, int min, int max) {\n return helpers.Helper.run(data, min, max);\n}\n```\n\nЭтот код необходим для проверки решения автоматическими тестами\n\n### Алгоритм\n\n* Структуру дерева, которое будет использоваться при проверке вашего решения, можно посмотреть в директории *\\_\\_fixtures\\_\\_*\n","has_solution":true,"entity_name":"B-деревья"},"units":[{"id":7350,"name":"theory","url":"/courses/algorithms-trees/lessons/btrees/theory_unit"},{"id":8503,"name":"quiz","url":"/courses/algorithms-trees/lessons/btrees/quiz_unit"},{"id":8506,"name":"exercise","url":"/courses/algorithms-trees/lessons/btrees/exercise_unit"}],"links":[],"ordered_units":[{"id":7350,"name":"theory","url":"/courses/algorithms-trees/lessons/btrees/theory_unit"},{"id":8503,"name":"quiz","url":"/courses/algorithms-trees/lessons/btrees/quiz_unit"},{"id":8506,"name":"exercise","url":"/courses/algorithms-trees/lessons/btrees/exercise_unit"}],"id":3314,"slug":"btrees","state":"approved","name":"B-деревья","course_order":140,"goal":"Познакомимся с B-деревьями и особенностями реализации операций с ними","self_study":null,"theory_video_provider":null,"theory_video_uid":null,"theory":"Ранее в курсе мы уже познакомились со сбалансированными деревьями поиска — это АВЛ-деревья или красно-черные деревья.\n\nОни способны организовать эффективный поиск элементов за время `logN`. Но чтобы совершить этот поиск, потребуется выполнить `logN` операций. Со временем число данных, которые нужно хранить в дереве, будет расти. Дерево потребуется сохранять на более дешевых хранилищах данных вроде жестких дисков, а не хранить в оперативной памяти.\n\nЭто ведет к тому, что для поиска элемента в дереве нам придется `logN` раз обратиться к жесткому диску. При больших `N` это число операций остается существенным. Операции над жестким диском гораздо медленнее, чем над оперативной памятью. Значит, оборудование будет быстро изнашиваться, а само приложение будет работать медленнее.\n\nУченым предстояло решить, как организовать эффективный поиск в древовидных структурах, которые должны храниться в постоянной памяти. Чтобы решить эту задачу, они придумали новый вид деревьев — сильноветвящиеся B-деревья и их производные: B+ деревья, B*-деревья, 2-3 деревья.\n\nВ этом уроке мы детально познакомимся с видами сильноветвящихся деревьев и особенностями реализации операций поиска, вставки и удаления узлов.\n\n## Устройство B-деревьев\n\nРассмотрим дерево, которое состоит из миллиона элементов. Если хранить данные в сбалансированном бинарном дереве поиска, то поиск элемента займет двадцать операций:\n\n`log2(1000000) = 19,932`\n\nЕсли разбить дерево на страницы, в каждой из которых будет по семь узлов дерева, поиск поддерева с нужным элементом будет выполнен за семь обращений к диску:\n\n`log(7+1) 1000000 = 6,644`\n\nРассмотрим пример такого разбиения:\n\n\n\nТакая группировка узлов на страницах превращает бинарное дерево в октарное — с восемью дочерними узлами. Число дочерних узлов у страницы может и дальше увеличиваться, например, до 128 элементов. Это приведет к тому, что поиск элемента будет выполнен всего за три обращения к диску:\n\n`log128(1000000) = 2,847`\n\nТаким образом, нам достаточно выбрать оптимальный размер страницы, который удовлетворяет нашим ограничениям по оперативной памяти. Также мы можем хранить в оперативной памяти ссылку на корневой элемент дерева, а сам вид дерева можно привести к виду на рисунке:\n\n\n\nВ этом случае в узлах располагается несколько ключей в порядке возрастания слева направо. Дочерние узлы содержат ключи, которые находятся в промежутке между значениями родительского узла.\n\nПомимо особенности расположения ключей стоит отметить, что B-дерево со степенью `m` обладает следующими свойствами:\n\n* Глубина всех листьев одинакова\n* Каждый узел имеет не более `m` потомков\n* Каждый узел кроме корневого и листовых имеют не менее `m/2` потомков\n* Если высота дерева больше единицы, то у корневого узла не менее двух дочерних узлов\n* Нелистовой узел с `k` потомками имеет `k-1` ключей\n\nПредставим узел B-дерева в виде кода на JavaScript:\n\n```javascript\nclass BTreeNode {\n constructor(value, parent) {\n this.leaf = false // Флаг, который показывает, что текущий узел является листовым\n this.keys = [value] // Массив ключей (полезной нагрузки) узла\n this.parent = parent // Cсылка на родителя\n this.children = [] // Массив дочерних узлов\n }\n}\n```\n\n```java\npublic class BTreeNode {\n public boolean leaf; // Флаг показывает, что текущий узел является листовым\n public List<Integer> keys; // Массив ключей (полезной нагрузки) узла\n public BTreeNode parent; // Cсылка на родителя\n public List<BTreeNode> children; // Массив дочерних узлов\n\n public BTreeNode(int value, BTreeNode parent) {\n this.leaf = false;\n this.keys = new ArrayList<>();\n this.keys.add(value);\n this.parent = parent;\n this.children = new ArrayList<>();\n }\n}\n```\n\n```python\nclass BTreeNode:\n def __init__(self, value, parent=None):\n self.leaf = False # Флаг, который показывает, что текущий узел является листовым\n self.keys = [value] # Массив ключей (полезной нагрузки) узла\n self.parent = parent # Cсылка на родителя\n self.children = [] # Массив дочерних узлов\n```\n\n```php\n<?php\n\nclass BTreeNode\n{\n public $leaf = false; // Флаг показывает, что текущий узел является листовым\n public $keys = []; // Массив ключей (полезной нагрузки) узла\n public $parent; // Cсылка на родителя\n public $children = []; // Массив дочерних узлов\n\n public function __construct($value, $parent = null)\n {\n $this->keys = [$value];\n $this->parent = $parent;\n }\n}\n```\n\nНад B-деревьями выполняются все классические операции:\n\n* Поиск узла\n* Добавление узла\n* Удаление узла\n\nОднако сложная организация ветвления узлов вносит свои реализации. Далее рассмотрим эти операции подробнее.\n\n## Операции над B-деревьями\n\nПоиск узлов в случае работы с B-деревом отличается от аналогичной операции над бинарным деревом только порядком действий во время проверки ключей узла. Он будет выглядеть следующим образом:\n\n```javascript\nclass BTreeNode {\n // ...\n\n findNode(value) {\n let node = this\n while (node) { // Проходимся по всем узлам\n for (let i = 0; i < node.keys.length; i++) { // Проверяем ключи\n if (value === node.keys[i]) {\n return node\n }\n if (value < node.keys[i]) {\n if (!node.leaf) {\n if (i < node.children.length) {\n node = node.children[i]\n }\n else {\n return null\n }\n break\n }\n else {\n return null\n }\n }\n else if (i === node.keys.length - 1 && !node.leaf) {\n if (i + 1 < node.children.length) {\n node = node.children[i + 1]\n }\n else {\n return null\n }\n break\n }\n }\n }\n return null\n }\n}\n```\n\n```java\nclass BTreeNode {\n // ...\n public BTreeNode findNode(int value) {\n BTreeNode node = this;\n while (node != null) {\n for (int i = 0; i < node.keys.size(); i++) {\n if (value == node.keys.get(i)) {\n return node;\n }\n if (value < node.keys.get(i)) {\n if (!node.leaf) {\n if (i < node.children.size()) {\n node = node.children.get(i);\n } else {\n return null;\n }\n break;\n } else {\n return null;\n }\n } else if (i == node.keys.size() - 1 && !node.leaf) {\n if (i + 1 < node.children.size()) {\n node = node.children.get(i + 1);\n } else {\n return null;\n }\n break;\n }\n }\n }\n return null;\n }\n}\n```\n\n```python\nclass BTreeNode:\n ## ...\n\n def find_node(self, value):\n node = self\n while node:\n for i in range(len(node.keys)):\n if value == node.keys[i]:\n return node\n if value < node.keys[i]:\n if not node.leaf:\n if i < len(node.children): # Проверяем, что индекс i не выходит за пределы массива\n node = node.children[i]\n else:\n return None\n break\n else:\n return None\n elif i == len(node.keys) - 1 and not node.leaf:\n if i + 1 < len(node.children): # Проверяем, что индекс i + 1 не выходит за пределы массива\n node = node.children[i + 1]\n else:\n return None\n break\n else:\n break\n return None\n```\n\n```php\n<?php\nclass BTreeNode\n{\n // ...\n public function findNode($value) {\n $node = $this;\n while ($node != null) {\n for ($i = 0; $i < count($node->keys); $i++) {\n if ($value == $node->keys[$i]) {\n return $node;\n }\n if ($value < $node->keys[$i]) {\n if (!$node->leaf) {\n if ($i < count($node->children)) {\n $node = $node->children[$i];\n } else {\n return null;\n }\n break;\n } else {\n return null;\n }\n } elseif ($i == count($node->keys) - 1 && !$node->leaf) {\n if ($i + 1 < count($node->children)) {\n $node = $node->children[$i + 1];\n } else {\n return null;\n }\n break;\n }\n }\n if ($node === null) {\n break;\n }\n }\n return null;\n }\n}\n```\n\nВ этом примере можно заметить пересечение с логикой поиска в бинарном дереве поиска. Если искомое значение меньше текущего значения узла, мы переходим по левой от него ветке. Если больше всех ключей узла — переходим на правое поддерево.\n\nВставка новых элементов в B-дерево разрешается только в листовые узлы. Это приводит к необходимости следить за заполненностью узлов. Если при вставке превысилась максимальная степень узла, то узел нужно разделять на части.\n\nЧтобы разделить узел, создается два новых листовых узла, которые содержат половину значений из существующего узла, и переносится среднее значение в родительский узел.\n\nЕсли заполнен и корневой узел, то мы разбиваем его на два новых: выбираем среднее значение, создаем для него новый узел, который станет новым корнем всего дерева:\n\n\n\nВ данном примере мы вставляем ключ 3 в дерево с одним заполненным корневым узлом. Вставка ключа приводит к переполнению корневого узла. Чтобы решить эту ситуацию, мы разбиваем корневой узел на две части, создаем новый узел со средним значением и делаем его корнем всего дерева.\n\nАналогично изменение структуры узлов может возникнуть, когда узел удаляется. Если в соседних узлах слишком мало ключей — занятость узлов падает ниже значения `m/2` — и эти узлы находятся на одном родственном уровне, то такие узлы необходимо слить. Данная ситуация называется **антипереполнением**.\n\nСуществует два способа объединения узлов:\n\n* Если у двух смежных узлов общий предок, и их содержимые помещаются в один узел, их следует объединить\n* Если содержимое смежных узлов не помещается в одном узле, то ключи перераспределяются между ними, чтобы восстановить баланс\n\nОперации слияния и расщепления достаточно дорогостоящие. Чтобы оптимизировать данный процесс, были придуманы специальные подвиды B-деревьев.\n\n## Производные виды деревьев\n\nК производным видам B-деревьев чаще всего относят следующие три вида:\n\n* B⁺-деревья\n* B*-деревья\n* 2-3-деревья\n\n### B⁺-деревья\n\nВ B⁺-деревьях данные ключей хранятся только в листовых узлах, а в промежуточных хранятся копии значений ключей. Это помогает эффективно организовывать поиск в блочных средах хранения. Например, в файловых системах, где B⁺-деревья применяют, чтобы хранить каталоги.\n\nТакже реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle, поддерживают этот тип деревьев, чтобы организовывать табличные индексы.\n\n### B*-деревья\n\nB*-дерево ориентировано на более плотное хранение ключей во внутренних узлах. Этот вариант гарантирует, что некорневые узлы заполнены как минимум на две трети от `m` вместо половины от `m`.\n\nB*-деревья используются для того, чтобы вызывать дорогостоящую операцию разделения как можно реже. Чтобы достичь этого, вместо немедленного разделения узла при его заполнении, его ключи «переливаются» в соседний узел. Если же и соседний узел заполнен, то ключи приблизительно поровну разделяются на три новых узла.\n\n### 2-3-деревья\n\n2-3 деревья — частный случай B⁺-деревьев с сокращенным количеством элементов на страницах. Каждый узел 2-3-дерева, кроме листовых, может содержать только один ключ и два потомка, либо два ключа и три потомка.\n\n## Выводы\n\nСпособ хранения деревьев может оказывать существенное влияние на организацию структуры узлов и входящих в них ключей. Например, хранение классических бинарных деревьев поиска на жестком диске может привести к многократному росту числа операций над диском.\n\nДля оптимизации хранения и поиска данных в таких условиях были предложены B-деревья. Они помогают сократить нагрузку на диск. Это возможно, если увеличить количество веток в узлах и хранить несколько ключей полезной нагрузки.\n"},"lessonMember":null,"courseMember":null,"course":{"start_lesson":{"exercise":{"id":2482,"slug":"algorithms_trees_concept_exercise","name":null,"state":"active","kind":"exercise","language":"javascript","locale":"ru","has_web_view":false,"has_test_view":false,"reviewable":true,"readme":"Напишите функцию, которая принимает содержание книги и возвращает маркированный список-оглавление.\n\n## solutions/solution.js\n\nРеализуйте и экспортируйте по умолчанию функцию, которая принимает содержание книги в виде массива объектов и возвращает строку – маркированный список-оглавление следующего вида:\n\n```text\nChapter 1: Sorting Spells\n* 1.1 Bubble Sort\n* 1.2 Insertion Sort\n* 1.3 Merge Sort\n* 1.4 Quick Sort\nChapter 2: Graphical Charms\n* 2.1 Graph Traversal\n* * 2.1.1 Breadth-First Search\n* * 2.1.2 Depth-First Search\n...\n```\n\nСтруктуру объекта с содержанием книги можно посмотреть в файле *\\_\\_fixtures\\_\\_/table_of_contents.json*\n\n```javascript\nimport solution from './solution.js';\n\nsolution(book);\n// Chapter 1: Sorting Spells\n// * 1.1 Bubble Sort\n// * 1.2 Insertion Sort\n// * 1.3 Merge Sort\n// * 1.4 Quick Sort\n// Chapter 2: Graphical Charms\n// * 2.1 Graph Traversal\n// * * 2.1.1 Breadth-First Search\n// * * 2.1.2 Depth-First Search\n// ...\n```\n\n## solutions/solution.php\n\nРеализуйте и экспортируйте по умолчанию функцию, которая принимает содержание книги в виде ассоциативного массива и возвращает строку – маркированный список-оглавление. Структуру ассоциативного массива с содержанием книги можно посмотреть в файле *\\_\\_fixtures\\_\\_/table_of_contents.json*\n\n```php\n<?php\n\nsolution(book);\n// Chapter 1: Sorting Spells\n// * 1.1 Bubble Sort\n// * 1.2 Insertion Sort\n// * 1.3 Merge Sort\n// * 1.4 Quick Sort\n// Chapter 2: Graphical Charms\n// * 2.1 Graph Traversal\n// * * 2.1.1 Breadth-First Search\n// * * 2.1.2 Depth-First Search\n// ...\n```\n\n## solutions/solution.py\n\nРеализуйте и экспортируйте по умолчанию функцию, которая принимает содержание книги в виде списка словарей и возвращает строку – маркированный список-оглавление. Структуру списка с содержанием книги можно посмотреть в файле *\\_\\_fixtures\\_\\_/table_of_contents.json*\n\n```python\nimport solution from solution\n\nsolution(book)\n# Chapter 1: Sorting Spells\n# * 1.1 Bubble Sort\n# * 1.2 Insertion Sort\n# * 1.3 Merge Sort\n# * 1.4 Quick Sort\n# Chapter 2: Graphical Charms\n# * 2.1 Graph Traversal\n# * * 2.1.1 Breadth-First Search\n# * * 2.1.2 Depth-First Search\n# ...\n```\n\n## solutions/Solution.java\n\nВ файле определите пакет `solutions` и создайте в нем публичный класс `Solution`. В классе реализуйте публичный статический метод `run()`, который принимает содержание книги в виде списка мап `List<Map<String, Object>>`. Метод должен вернуть строку – маркированный список-оглавление\n\nСтруктуру списка с содержанием книги можно посмотреть в файле *\\_\\_fixtures\\_\\_/table_of_contents.json*\n\n```java\nimport solutions.Solution;\n\nSolution.run(book);\n\n// Chapter 1: Sorting Spells\n// * 1.1 Bubble Sort\n// * 1.2 Insertion Sort\n// * 1.3 Merge Sort\n// * 1.4 Quick Sort\n// Chapter 2: Graphical Charms\n// * 2.1 Graph Traversal\n// * * 2.1.1 Breadth-First Search\n// * * 2.1.2 Depth-First Search\n// ...\n```\n","prepared_readme":"Напишите функцию, которая принимает содержание книги и возвращает маркированный список-оглавление.\n\n## solutions/solution.js\n\nРеализуйте и экспортируйте по умолчанию функцию, которая принимает содержание книги в виде массива объектов и возвращает строку – маркированный список-оглавление следующего вида:\n\n```text\nChapter 1: Sorting Spells\n* 1.1 Bubble Sort\n* 1.2 Insertion Sort\n* 1.3 Merge Sort\n* 1.4 Quick Sort\nChapter 2: Graphical Charms\n* 2.1 Graph Traversal\n* * 2.1.1 Breadth-First Search\n* * 2.1.2 Depth-First Search\n...\n```\n\nСтруктуру объекта с содержанием книги можно посмотреть в файле *\\_\\_fixtures\\_\\_/table_of_contents.json*\n\n```javascript\nimport solution from './solution.js';\n\nsolution(book);\n// Chapter 1: Sorting Spells\n// * 1.1 Bubble Sort\n// * 1.2 Insertion Sort\n// * 1.3 Merge Sort\n// * 1.4 Quick Sort\n// Chapter 2: Graphical Charms\n// * 2.1 Graph Traversal\n// * * 2.1.1 Breadth-First Search\n// * * 2.1.2 Depth-First Search\n// ...\n```\n\n## solutions/solution.php\n\nРеализуйте и экспортируйте по умолчанию функцию, которая принимает содержание книги в виде ассоциативного массива и возвращает строку – маркированный список-оглавление. Структуру ассоциативного массива с содержанием книги можно посмотреть в файле *\\_\\_fixtures\\_\\_/table_of_contents.json*\n\n```php\n<?php\n\nsolution(book);\n// Chapter 1: Sorting Spells\n// * 1.1 Bubble Sort\n// * 1.2 Insertion Sort\n// * 1.3 Merge Sort\n// * 1.4 Quick Sort\n// Chapter 2: Graphical Charms\n// * 2.1 Graph Traversal\n// * * 2.1.1 Breadth-First Search\n// * * 2.1.2 Depth-First Search\n// ...\n```\n\n## solutions/solution.py\n\nРеализуйте и экспортируйте по умолчанию функцию, которая принимает содержание книги в виде списка словарей и возвращает строку – маркированный список-оглавление. Структуру списка с содержанием книги можно посмотреть в файле *\\_\\_fixtures\\_\\_/table_of_contents.json*\n\n```python\nimport solution from solution\n\nsolution(book)\n# Chapter 1: Sorting Spells\n# * 1.1 Bubble Sort\n# * 1.2 Insertion Sort\n# * 1.3 Merge Sort\n# * 1.4 Quick Sort\n# Chapter 2: Graphical Charms\n# * 2.1 Graph Traversal\n# * * 2.1.1 Breadth-First Search\n# * * 2.1.2 Depth-First Search\n# ...\n```\n\n## solutions/Solution.java\n\nВ файле определите пакет `solutions` и создайте в нем публичный класс `Solution`. В классе реализуйте публичный статический метод `run()`, который принимает содержание книги в виде списка мап `List<Map<String, Object>>`. Метод должен вернуть строку – маркированный список-оглавление\n\nСтруктуру списка с содержанием книги можно посмотреть в файле *\\_\\_fixtures\\_\\_/table_of_contents.json*\n\n```java\nimport solutions.Solution;\n\nSolution.run(book);\n\n// Chapter 1: Sorting Spells\n// * 1.1 Bubble Sort\n// * 1.2 Insertion Sort\n// * 1.3 Merge Sort\n// * 1.4 Quick Sort\n// Chapter 2: Graphical Charms\n// * 2.1 Graph Traversal\n// * * 2.1.1 Breadth-First Search\n// * * 2.1.2 Depth-First Search\n// ...\n```\n","has_solution":true,"entity_name":"Деревья как концепция"},"units":[{"id":7043,"name":"theory","url":"/courses/algorithms-trees/lessons/concept/theory_unit"},{"id":8500,"name":"quiz","url":"/courses/algorithms-trees/lessons/concept/quiz_unit"},{"id":8488,"name":"exercise","url":"/courses/algorithms-trees/lessons/concept/exercise_unit"}],"links":[],"ordered_units":[{"id":7043,"name":"theory","url":"/courses/algorithms-trees/lessons/concept/theory_unit"},{"id":8500,"name":"quiz","url":"/courses/algorithms-trees/lessons/concept/quiz_unit"},{"id":8488,"name":"exercise","url":"/courses/algorithms-trees/lessons/concept/exercise_unit"}],"id":3111,"slug":"concept","state":"approved","name":"Деревья как концепция","course_order":110,"goal":"Разбираемся, что такое деревья, для чего они нужны, какие формы деревьев бывают и как их представляют","self_study":null,"theory_video_provider":null,"theory_video_uid":null,"theory":"Иерархические структуры окружают нас везде — например, структура управления предприятием, адреса, содержания в книгах. Иерархия встречается и в программировании, например, в работе со стандартными типами данных, такими как массивы. Так как такие данные нельзя разместить линейно, программисты используют деревья. Они считаются одной из важнейших нелинейных структур, которые встречаются при работе с алгоритмами.\n\nВ этом уроке мы поговорим о деревьях, узнаем, какие проблемы они решают, и какие характеристики и способы представления деревьев существуют.\n\n## Что такое деревья и для чего они нужны\n\nДеревья используют, чтобы отразить в памяти компьютера иерархические взаимосвязи. Их применяют для реестра Windows, XML-документов, DOM-структур HTML-страниц, родословных, каталогов запчастей или файловых систем. Например, так файловую структуру видят конечные пользователи:\n\n\n\nПри этом для программистов она выглядит иначе:\n\n\n\nЭто древовидное представление структуры. Из этой схемы можно сделать вывод, что **дерево** — это конечное множество, которое состоит из **вершин** или **узлов**, а еще есть выделенный узел — **корень дерева**. В примере выше вершины — это все папки, а корень дерева — «Новая папка».\n\nКаждый узел содержит данные и ссылки на другие непересекающиеся между собой деревья. В этом случае каждая папка в дереве, от которой исходят другие данные, является для них **корневым узлом**. При этом эти данные образуют поддерево основного дерева.\n\nПомимо представления иерархических взаимосвязей, деревья применяют в следующих случаях:\n\n* Организация быстрого поиска в отсортированных данных, например, в индексах баз ��анных\n* Кластеризация данных. Возможность разбивать данные на кластеры применяется в базах данных и машинном обучении\n* Решение сложных арифметических выражений. Дерево используется, чтобы хранить порядок выполнения операций, значений аргументов и промежуточных результатов\n* Алгоритмы принятия решений. Дерево решений — инструмент интеллектуального анализа данных и проведения предсказаний. Он считается более простым в работе инструментом, чем нейросети, так как формулирует правила на естественном языке\n* Сетевое взаимодействие. Деревья используют для маршрутизации и работы механизмов определения IP-адресов по URL сайта, например, DNS-сервера\n\nДеревья часто используют в проектах по разработке программ. Как результат — разработчики выделили терминологию описания узлов и формы деревьев.\n\n## Какие узлы есть в деревьях\n\nТак как внешний вид дерева схож с генеалогическим деревом, термины генеалогии применяются и в программировании. Например, в отношении алгоритмических деревьев можно услышать такие термины, как «основатель династии», «мама», «ребенок», «брат», «двоюродный дядя». При этом существуют стандартизированные именования для отношений узлов:\n\n* **Родительский узел** или **предок** — узел, который находится на первом уровне иерархии\n* **Дочерний узел** или **потомок** — узел, на который есть ссылки из рассматриваемого узла\n* **Корневой узел** — узел, на который нет ссылок из других узлов\n* **Сестринские узлы** — два узла, у которых общие родители\n* **Листовой узел**, **лист дерева** или **терминальный узел** — узел, у которого количество поддеревьев равно нулю\n* **Узел ветвления** или **внутренняя вершина** — узел, у которого есть дочерние структуры\n\nКоличество поддеревьев у узла называется его **степенью***. Максимальное значение степени узла — **степень дерева**. Если степень дерева равна двум, значит, у каждого узла может быть не более двух потомков:\n\n\n\n## Какие формы деревьев бывают\n\nИз-за определенных особенностей задач и алгоритмов, разработчики применяют разные формы деревьев со своими особенностями организации вершин:\n\n* **Упорядоченное дерево** — дерево, в котором все вершины отсортированы. Такие деревья еще называются **плоскими**, так как при последовательном обходе вершин получится отсортированный массив:\n\n\n\n Далее в курсе мы будем считать все деревья упорядоченными, если в условии не сказано обратное.\n\n* **Полное дерево** — дерево, в котором количество дочерних узлов у каждой внутренней вершины равно степени дерева:\n\n\n\n* **Завершенное дерево** – дерево, у которого каждый уровень, кроме последнего, является полным:\n\n\n\n* **Идеальное дерево** — полное дерево, у которого все терминальные узлы располагаются на одном уровне:\n\n\n\nМы познакомились с основной терминологией, которая используется при работе с деревьями. Теперь рассмотрим, какие есть способы представления деревьев в графическом виде и в коде.\n\n## Как могут выглядеть деревья\n\nЧтобы изображать иерархические структуры, используют следующие варианты:\n\n* Древовидное схематическое представление\n* Круги Эйлера\n* Списки с отступами\n* Код\n\nРазберем каждый способ изображения дерева.\n\n### Древовидное схематическое представление\n\nВ качестве основного способа представления деревьев используют имена, номера вершин или содержимое полезных данных узла. Они соединяются линиями, которые обозначают связи между вершинами:\n\n\n\nЭтот способ похож на природные деревья, только в информатике корень дерева обычно рисуется вверху схемы.\n\n### Круги Эйлера\n\nМы можем изобразить алгоритмическое дерево по правилам теории множеств с помощью кругов Эйлера:\n\n\n\nДанный способ на практике встречается достаточно редко, так как поддеревья обычно не пересекаются между собой. В такой ситуации использование схематичного представления более наглядно для человека.\n\n### Списки с отступами\n\nИерархическую связь можно изображать через пронумерованный список с отступами, где отступ или номер строки будут означать ее уровень:\n\n\n\nТакой формат используют при работе с книгой, так как оглавление — это дерево.\n\n### Код\n\nЧтобы работать с деревьями, их нужно уметь не только рисовать, но и хранить в памяти компьютера.\n\nВ виде кода мы получаем следующий класс узла:\n\n```javascript\nclass BinaryTreeNode {\n constructor(value, parent) {\n this.child1 = null\n this.child2 = null\n this.parent = parent\n this.value = value\n }\n}\n ```\n\n```java\nclass BinaryTreeNode {\n public BinaryTreeNode child1 = null;\n public BinaryTreeNode child2 = null;\n public BinaryTreeNode parent;\n public Object value;\n\n BinaryTreeNode(Object value, BinaryTreeNode parent) {\n this.parent = parent;\n this.value = value;\n }\n}\n```\n\n```python\nclass BinaryTreeNode:\n def __init__(self, value, parent=None):\n self.child1 = None\n self.child2 = None\n self.parent = parent\n self.value = value\n```\n\n```php\n<?php\nclass BinaryTreeNode\n{\n public ?BinaryTreeNode $child1 = null;\n public ?BinaryTreeNode $child2 = null;\n public ?BinaryTreeNode $parent = null;\n public $value;\n\n public function __construct($value, BinaryTreeNode $parent)\n {\n $this->parent = $parent;\n $this->value = $value;\n }\n}\n```\n\nЧтобы организовать из узла дерево, нужно добавить методы, которые заполняют ссылки на поддеревья `child1` и `child2`. Как реализуются деревья в коде, разберем подробно в следующих уроках.\n\nПрежде чем писать код дерева, разработчики часто изображают иерархию графически, чтобы видеть полную картину взаимосвязей.\n\n## Выводы\n\nМы познакомились с такой структурой данных как деревья. Они используются, чтобы хранить информацию в иерархическом виде, индексировать и кластеризировать большие последовательности данных.\n\nВ этом уроке мы также познакомились с основными обозначениями узлов, а также различными формами деревьев. Еще рассмотрели способы представления дерева — можно изображать иерархию с помощью схемы, кругов Эйлера, списком с отступами, а также в коде.\n"},"id":288,"slug":"algorithms-trees","challenges_count":0,"name":"Алгоритмы на деревьях","allow_indexing":true,"state":"approved","course_state":"finished","pricing_type":"paid","description":"В этом курсе вы научитесь работать с древовидными структурами данных. Вы узнаете, зачем нужны деревья, как с их помощью сделать быстрый поиск в словаре и на карте, и почему базы данных работают так быстро. Еще познакомитесь со специальными видами деревьев, которые используются в браузере и компиляторах.","kind":"additional","updated_at":"2026-02-12T14:03:27.752Z","language":"javascript","duration_cache":37800,"skills":["Создавать алгоритмы для древовидных структур","Использовать рекурсию для обхода деревьев","Выбирать эффективную структуру данных для решения задач","Создавать поиск ближайших мест"],"keywords":[],"lessons_count":8,"cover":"https://hexlet.io/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6MTQyNjcsInB1ciI6ImJsb2JfaWQifX0=--9de1210451f6271cde3b5c010530f2d03e819ef5/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJwbmciLCJyZXNpemVfdG9fZmlsbCI6WzYwMCw0MDBdfSwicHVyIjoidmFyaWF0aW9uIn19--6067466c2912ca31a17eddee04b8cf2a38c6ad17/image.png"},"recommendedLandings":[{"stack":{"id":34,"slug":"algorithms","title":"Алгоритмы и структуры данных","audience":"for_programmers","start_type":"anytime","pricing_model":"subscription","priority":"medium","kind":"track","state":"published","stack_state":"finished","order":4000,"duration_in_months":2},"id":56,"slug":"algorithms","title":"Алгоритмы и структуры данных","subtitle":"Навык, который увеличит ваши шансы пройти алгоритмическое интервью в международные компании на 80%","subtitle_for_lists":"Алгоритмы для собеседований","locale":"ru","current":true,"duration_in_months_text":"2 месяца","stack_slug":"algorithms","price_text":"от 3 900 ₽","duration_text":"2 месяца","cover_list_variant":"https://hexlet.io/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6NDAyOCwicHVyIjoiYmxvYl9pZCJ9fQ==--ae9eed98663dd1201759d042a5ba7ca790866156/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJ3ZWJwIiwicmVzaXplX3RvX2xpbWl0IjpbNDAwLDQwMF0sInNhdmVyIjp7InF1YWxpdHkiOjg1fX0sInB1ciI6InZhcmlhdGlvbiJ9fQ==--5b6f46dacd1af664f27558553a58076185091823/Programming-bro.png"}],"lessonMemberUnit":null,"accessToLearnUnitExists":false,"accessToCourseExists":false},"url":"/courses/algorithms-trees/lessons/btrees/theory_unit","version":"8f286f6358a90a7bef2263b3a6edf5a90a94fa42","encryptHistory":false,"clearHistory":false}"><style data-mantine-styles="true">:root, :host{--mantine-font-family: Arial, sans-serif;--mantine-font-family-headings: Arial, sans-serif;--mantine-heading-font-weight: normal;--mantine-radius-default: 0rem;--mantine-primary-color-filled: var(--mantine-color-indigo-filled);--mantine-primary-color-filled-hover: var(--mantine-color-indigo-filled-hover);--mantine-primary-color-light: var(--mantine-color-indigo-light);--mantine-primary-color-light-hover: var(--mantine-color-indigo-light-hover);--mantine-primary-color-light-color: var(--mantine-color-indigo-light-color);--mantine-spacing-xxl: calc(4rem * var(--mantine-scale));--mantine-font-size-xs: 12px;--mantine-font-size-sm: 14px;--mantine-font-size-md: 16px;--mantine-font-size-lg: clamp(16.0000px, calc(15.2727px + 0.2273vw), 18.0000px);--mantine-font-size-xl: clamp(16.0000px, calc(14.5455px + 0.4545vw), 20.0000px);--mantine-font-size-display-3: clamp(32.0000px, calc(26.1818px + 1.8182vw), 48.0000px);--mantine-font-size-display-2: clamp(36.0000px, calc(25.8182px + 3.1818vw), 64.0000px);--mantine-font-size-display-1: clamp(40.0000px, calc(25.4545px + 4.5455vw), 80.0000px);--mantine-font-size-h1: clamp(28.0000px, calc(23.6364px + 1.3636vw), 40.0000px);--mantine-font-size-h2: clamp(24.0000px, calc(21.0909px + 0.9091vw), 32.0000px);--mantine-font-size-h3: clamp(20.0000px, calc(17.0909px + 0.9091vw), 28.0000px);--mantine-font-size-h4: clamp(16.0000px, calc(13.0909px + 0.9091vw), 24.0000px);--mantine-font-size-h5: clamp(16.0000px, calc(14.5455px + 0.4545vw), 20.0000px);--mantine-font-size-h6: 1rem;--mantine-primary-color-0: var(--mantine-color-indigo-0);--mantine-primary-color-1: var(--mantine-color-indigo-1);--mantine-primary-color-2: var(--mantine-color-indigo-2);--mantine-primary-color-3: var(--mantine-color-indigo-3);--mantine-primary-color-4: var(--mantine-color-indigo-4);--mantine-primary-color-5: var(--mantine-color-indigo-5);--mantine-primary-color-6: var(--mantine-color-indigo-6);--mantine-primary-color-7: var(--mantine-color-indigo-7);--mantine-primary-color-8: var(--mantine-color-indigo-8);--mantine-primary-color-9: var(--mantine-color-indigo-9);--mantine-color-red-0: #ffeaea;--mantine-color-red-1: #fed4d4;--mantine-color-red-2: #f4a7a8;--mantine-color-red-3: #ec7878;--mantine-color-red-4: #e55050;--mantine-color-red-5: #e03131;--mantine-color-red-6: #e02829;--mantine-color-red-7: #c71a1c;--mantine-color-red-8: #b21218;--mantine-color-red-9: #9c0411;--mantine-color-violet-0: #fce9ff;--mantine-color-violet-1: #f1cfff;--mantine-color-violet-2: #e09bff;--mantine-color-violet-3: #d16fff;--mantine-color-violet-4: #be37fe;--mantine-color-violet-5: #b51afe;--mantine-color-violet-6: #b009ff;--mantine-color-violet-7: #9b00e4;--mantine-color-violet-8: #8a00cc;--mantine-color-violet-9: #7800b3;--mantine-color-indigo-0: #edecff;--mantine-color-indigo-1: #d6d5fe;--mantine-color-indigo-2: #aaa9f4;--mantine-color-indigo-3: #7b79eb;--mantine-color-indigo-4: #5451e4;--mantine-color-indigo-5: #3b37e0;--mantine-color-indigo-6: #2d2adf;--mantine-color-indigo-7: #1f1ec7;--mantine-color-indigo-8: #1819b2;--mantine-color-indigo-9: #0c149e;--mantine-color-cyan-0: #dffdff;--mantine-color-cyan-1: #caf5ff;--mantine-color-cyan-2: #99e8ff;--mantine-color-cyan-3: #64daff;--mantine-color-cyan-4: #3ccffe;--mantine-color-cyan-5: #24c8fe;--mantine-color-cyan-6: #00c2ff;--mantine-color-cyan-7: #00ade4;--mantine-color-cyan-8: #009acd;--mantine-color-cyan-9: #0085b5;--mantine-color-green-0: #e9fdec;--mantine-color-green-1: #d7f6dc;--mantine-color-green-2: #b0eab9;--mantine-color-green-3: #86df94;--mantine-color-green-4: #62d574;--mantine-color-green-5: #4ccf5f;--mantine-color-green-6: #3fcc54;--mantine-color-green-7: #2fb344;--mantine-color-green-8: #25a03b;--mantine-color-green-9: #138a2e;--mantine-color-yellow-0: #fff7e2;--mantine-color-yellow-1: #ffeecd;--mantine-color-yellow-2: #ffdc9c;--mantine-color-yellow-3: #ffc966;--mantine-color-yellow-4: #feb93a;--mantine-color-yellow-5: #feae1e;--mantine-color-yellow-6: #ffa90f;--mantine-color-yellow-8: #ca8200;--mantine-color-yellow-9: #af7000;--mantine-h1-font-size: clamp(28.0000px, calc(23.6364px + 1.3636vw), 40.0000px);--mantine-h1-font-weight: normal;--mantine-h2-font-size: clamp(24.0000px, calc(21.0909px + 0.9091vw), 32.0000px);--mantine-h2-font-weight: normal;--mantine-h3-font-size: clamp(20.0000px, calc(17.0909px + 0.9091vw), 28.0000px);--mantine-h3-font-weight: normal;--mantine-h4-font-size: clamp(16.0000px, calc(13.0909px + 0.9091vw), 24.0000px);--mantine-h4-font-weight: normal;--mantine-h5-font-size: clamp(16.0000px, calc(14.5455px + 0.4545vw), 20.0000px);--mantine-h5-font-weight: normal;--mantine-h6-font-size: 1rem;--mantine-h6-font-weight: normal;}
:root[data-mantine-color-scheme="dark"], :host([data-mantine-color-scheme="dark"]){--mantine-color-anchor: var(--mantine-color-text);--mantine-color-dimmed: #495057;--mantine-color-dark-filled: var(--mantine-color-dark-5);--mantine-color-dark-filled-hover: var(--mantine-color-dark-6);--mantine-color-dark-light: rgba(105, 105, 105, 0.15);--mantine-color-dark-light-hover: rgba(105, 105, 105, 0.2);--mantine-color-dark-light-color: var(--mantine-color-dark-0);--mantine-color-dark-outline: var(--mantine-color-dark-1);--mantine-color-dark-outline-hover: rgba(184, 184, 184, 0.05);--mantine-color-gray-filled: var(--mantine-color-gray-5);--mantine-color-gray-filled-hover: var(--mantine-color-gray-6);--mantine-color-gray-light: rgba(222, 226, 230, 0.15);--mantine-color-gray-light-hover: rgba(222, 226, 230, 0.2);--mantine-color-gray-light-color: var(--mantine-color-gray-0);--mantine-color-gray-outline: var(--mantine-color-gray-1);--mantine-color-gray-outline-hover: rgba(241, 243, 245, 0.05);--mantine-color-red-filled: var(--mantine-color-red-5);--mantine-color-red-filled-hover: var(--mantine-color-red-6);--mantine-color-red-light: rgba(236, 120, 120, 0.15);--mantine-color-red-light-hover: rgba(236, 120, 120, 0.2);--mantine-color-red-light-color: var(--mantine-color-red-0);--mantine-color-red-outline: var(--mantine-color-red-1);--mantine-color-red-outline-hover: rgba(254, 212, 212, 0.05);--mantine-color-pink-filled: var(--mantine-color-pink-5);--mantine-color-pink-filled-hover: var(--mantine-color-pink-6);--mantine-color-pink-light: rgba(250, 162, 193, 0.15);--mantine-color-pink-light-hover: rgba(250, 162, 193, 0.2);--mantine-color-pink-light-color: var(--mantine-color-pink-0);--mantine-color-pink-outline: var(--mantine-color-pink-1);--mantine-color-pink-outline-hover: rgba(255, 222, 235, 0.05);--mantine-color-grape-filled: var(--mantine-color-grape-5);--mantine-color-grape-filled-hover: var(--mantine-color-grape-6);--mantine-color-grape-light: rgba(229, 153, 247, 0.15);--mantine-color-grape-light-hover: rgba(229, 153, 247, 0.2);--mantine-color-grape-light-color: var(--mantine-color-grape-0);--mantine-color-grape-outline: var(--mantine-color-grape-1);--mantine-color-grape-outline-hover: rgba(243, 217, 250, 0.05);--mantine-color-violet-filled: var(--mantine-color-violet-5);--mantine-color-violet-filled-hover: var(--mantine-color-violet-6);--mantine-color-violet-light: rgba(209, 111, 255, 0.15);--mantine-color-violet-light-hover: rgba(209, 111, 255, 0.2);--mantine-color-violet-light-color: var(--mantine-color-violet-0);--mantine-color-violet-outline: var(--mantine-color-violet-1);--mantine-color-violet-outline-hover: rgba(241, 207, 255, 0.05);--mantine-color-indigo-filled: var(--mantine-color-indigo-5);--mantine-color-indigo-filled-hover: var(--mantine-color-indigo-6);--mantine-color-indigo-light: rgba(123, 121, 235, 0.15);--mantine-color-indigo-light-hover: rgba(123, 121, 235, 0.2);--mantine-color-indigo-light-color: var(--mantine-color-indigo-0);--mantine-color-indigo-outline: var(--mantine-color-indigo-1);--mantine-color-indigo-outline-hover: rgba(214, 213, 254, 0.05);--mantine-color-blue-filled: var(--mantine-color-blue-5);--mantine-color-blue-filled-hover: var(--mantine-color-blue-6);--mantine-color-blue-light: rgba(116, 192, 252, 0.15);--mantine-color-blue-light-hover: rgba(116, 192, 252, 0.2);--mantine-color-blue-light-color: var(--mantine-color-blue-0);--mantine-color-blue-outline: var(--mantine-color-blue-1);--mantine-color-blue-outline-hover: rgba(208, 235, 255, 0.05);--mantine-color-cyan-filled: var(--mantine-color-cyan-5);--mantine-color-cyan-filled-hover: var(--mantine-color-cyan-6);--mantine-color-cyan-light: rgba(100, 218, 255, 0.15);--mantine-color-cyan-light-hover: rgba(100, 218, 255, 0.2);--mantine-color-cyan-light-color: var(--mantine-color-cyan-0);--mantine-color-cyan-outline: var(--mantine-color-cyan-1);--mantine-color-cyan-outline-hover: rgba(202, 245, 255, 0.05);--mantine-color-teal-filled: var(--mantine-color-teal-5);--mantine-color-teal-filled-hover: var(--mantine-color-teal-6);--mantine-color-teal-light: rgba(99, 230, 190, 0.15);--mantine-color-teal-light-hover: rgba(99, 230, 190, 0.2);--mantine-color-teal-light-color: var(--mantine-color-teal-0);--mantine-color-teal-outline: var(--mantine-color-teal-1);--mantine-color-teal-outline-hover: rgba(195, 250, 232, 0.05);--mantine-color-green-filled: var(--mantine-color-green-5);--mantine-color-green-filled-hover: var(--mantine-color-green-6);--mantine-color-green-light: rgba(134, 223, 148, 0.15);--mantine-color-green-light-hover: rgba(134, 223, 148, 0.2);--mantine-color-green-light-color: var(--mantine-color-green-0);--mantine-color-green-outline: var(--mantine-color-green-1);--mantine-color-green-outline-hover: rgba(215, 246, 220, 0.05);--mantine-color-lime-filled: var(--mantine-color-lime-5);--mantine-color-lime-filled-hover: var(--mantine-color-lime-6);--mantine-color-lime-light: rgba(192, 235, 117, 0.15);--mantine-color-lime-light-hover: rgba(192, 235, 117, 0.2);--mantine-color-lime-light-color: var(--mantine-color-lime-0);--mantine-color-lime-outline: var(--mantine-color-lime-1);--mantine-color-lime-outline-hover: rgba(233, 250, 200, 0.05);--mantine-color-yellow-filled: var(--mantine-color-yellow-5);--mantine-color-yellow-filled-hover: var(--mantine-color-yellow-6);--mantine-color-yellow-light: rgba(255, 201, 102, 0.15);--mantine-color-yellow-light-hover: rgba(255, 201, 102, 0.2);--mantine-color-yellow-light-color: var(--mantine-color-yellow-0);--mantine-color-yellow-outline: var(--mantine-color-yellow-1);--mantine-color-yellow-outline-hover: rgba(255, 238, 205, 0.05);--mantine-color-orange-filled: var(--mantine-color-orange-5);--mantine-color-orange-filled-hover: var(--mantine-color-orange-6);--mantine-color-orange-light: rgba(255, 192, 120, 0.15);--mantine-color-orange-light-hover: rgba(255, 192, 120, 0.2);--mantine-color-orange-light-color: var(--mantine-color-orange-0);--mantine-color-orange-outline: var(--mantine-color-orange-1);--mantine-color-orange-outline-hover: rgba(255, 232, 204, 0.05);--app-cta-gradient: linear-gradient(90deg, var(--mantine-color-blue-9) 0%, var(--mantine-color-cyan-7) 100%);--app-color-surface: #2e2e2e;}
:root[data-mantine-color-scheme="light"], :host([data-mantine-color-scheme="light"]){--mantine-color-anchor: var(--mantine-color-text);--mantine-color-dimmed: #495057;--mantine-color-red-light: rgba(224, 40, 41, 0.1);--mantine-color-red-light-hover: rgba(224, 40, 41, 0.12);--mantine-color-red-outline-hover: rgba(224, 40, 41, 0.05);--mantine-color-violet-light: rgba(176, 9, 255, 0.1);--mantine-color-violet-light-hover: rgba(176, 9, 255, 0.12);--mantine-color-violet-outline-hover: rgba(176, 9, 255, 0.05);--mantine-color-indigo-light: rgba(45, 42, 223, 0.1);--mantine-color-indigo-light-hover: rgba(45, 42, 223, 0.12);--mantine-color-indigo-outline-hover: rgba(45, 42, 223, 0.05);--mantine-color-cyan-light: rgba(0, 194, 255, 0.1);--mantine-color-cyan-light-hover: rgba(0, 194, 255, 0.12);--mantine-color-cyan-outline-hover: rgba(0, 194, 255, 0.05);--mantine-color-green-light: rgba(63, 204, 84, 0.1);--mantine-color-green-light-hover: rgba(63, 204, 84, 0.12);--mantine-color-green-outline-hover: rgba(63, 204, 84, 0.05);--mantine-color-yellow-light: rgba(255, 169, 15, 0.1);--mantine-color-yellow-light-hover: rgba(255, 169, 15, 0.12);--mantine-color-yellow-outline-hover: rgba(255, 169, 15, 0.05);--app-color-surface: #f1f3f5;--app-cta-gradient: linear-gradient(90deg, var(--mantine-color-blue-filled) 0%, var(--mantine-color-cyan-5) 100%);}</style><style data-mantine-styles="classes">@media (max-width: 35.99375em) {.mantine-visible-from-xs {display: none !important;}}@media (min-width: 36em) {.mantine-hidden-from-xs {display: none !important;}}@media (max-width: 47.99375em) {.mantine-visible-from-sm {display: none !important;}}@media (min-width: 48em) {.mantine-hidden-from-sm {display: none !important;}}@media (max-width: 61.99375em) {.mantine-visible-from-md {display: none !important;}}@media (min-width: 62em) {.mantine-hidden-from-md {display: none !important;}}@media (max-width: 74.99375em) {.mantine-visible-from-lg {display: none !important;}}@media (min-width: 75em) {.mantine-hidden-from-lg {display: none !important;}}@media (max-width: 87.99375em) {.mantine-visible-from-xl {display: none !important;}}@media (min-width: 88em) {.mantine-hidden-from-xl {display: none !important;}}</style><div style="position:absolute;top:0rem" class=""></div><div style="max-width:var(--container-size-xl);height:100%;min-height:0rem" class=""><style data-mantine-styles="inline">.__m__-_R_5ub_{--grid-gutter:0rem;}</style><div style="height:100%;min-height:0rem" class="m_410352e9 mantine-Grid-root __m__-_R_5ub_"><div class="m_dee7bd2f mantine-Grid-inner" style="height:100%"><style data-mantine-styles="inline">.__m__-_R_rdub_{--col-flex-grow:auto;--col-flex-basis:91.66666666666667%;--col-max-width:91.66666666666667%;}@media(min-width: 48em){.__m__-_R_rdub_{--col-flex-grow:auto;--col-flex-basis:83.33333333333334%;--col-max-width:83.33333333333334%;}}</style><div style="min-width:0rem;height:100%;min-height:0rem;display:flex" class="m_96bdd299 mantine-Grid-col __m__-_R_rdub_"><style data-mantine-styles="inline">.__m__-_R_6qrdub_{margin-top:0rem;padding-inline:var(--mantine-spacing-xs);width:100%;}@media(min-width: 48em){.__m__-_R_6qrdub_{margin-top:var(--mantine-spacing-xl);width:80%;}}@media(min-width: 62em){.__m__-_R_6qrdub_{padding-inline:var(--mantine-spacing-xl);}}</style><div style="margin-inline:auto;max-width:var(--mantine-breakpoint-xl)" class="__m__-_R_6qrdub_"><div style="color:var(--mantine-color-dimmed)" class="m_4451eb3a mantine-Center-root" data-inline="true"><div style="--ti-size:var(--ti-size-xs);--ti-bg:transparent;--ti-color:var(--mantine-color-indigo-light-color);--ti-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;margin-inline-end:calc(0.125rem * var(--mantine-scale));color:inherit" class="m_7341320d mantine-ThemeIcon-root" data-variant="transparent" data-size="xs"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-lock "><path d="M5 13a2 2 0 0 1 2 -2h10a2 2 0 0 1 2 2v6a2 2 0 0 1 -2 2h-10a2 2 0 0 1 -2 -2v-6"></path><path d="M11 16a1 1 0 1 0 2 0a1 1 0 0 0 -2 0"></path><path d="M8 11v-4a4 4 0 1 1 8 0v4"></path></svg></div><p style="font-size:var(--mantine-font-size-sm)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Алгоритмы на деревьях</p></div><h1 style="--title-fw:var(--mantine-h1-font-weight);--title-lh:var(--mantine-h1-line-height);--title-fz:var(--mantine-h1-font-size);margin-bottom:var(--mantine-spacing-xl)" class="m_8a5d1357 mantine-Title-root" data-order="1">Теория: B-деревья</h1><script type="application/ld+json">{"@context":"https://schema.org","@type":"LearningResource","name":"B-деревья","inLanguage":"ru","isPartOf":{"@type":"LearningResource","name":"Алгоритмы на деревьях"},"isAccessibleForFree":"False","hasPart":{"@type":"WebPageElement","isAccessibleForFree":"False","cssSelector":".paywalled"}}</script><div class=""><div style="--alert-color:var(--mantine-color-indigo-light-color);margin-bottom:var(--mantine-spacing-lg);font-size:var(--mantine-font-size-lg)" class="m_66836ed3 mantine-Alert-root" id="mantine-_R_remqrdub_" role="alert" aria-describedby="mantine-_R_remqrdub_-body" aria-labelledby="mantine-_R_remqrdub_-title"><div class="m_a5d60502 mantine-Alert-wrapper"><div class="m_667f2a6a mantine-Alert-icon"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-rocket "><path d="M4 13a8 8 0 0 1 7 7a6 6 0 0 0 3 -5a9 9 0 0 0 6 -8a3 3 0 0 0 -3 -3a9 9 0 0 0 -8 6a6 6 0 0 0 -5 3"></path><path d="M7 14a6 6 0 0 0 -3 6a6 6 0 0 0 6 -3"></path><path d="M14 9a1 1 0 1 0 2 0a1 1 0 1 0 -2 0"></path></svg></div><div class="m_667c2793 mantine-Alert-body"><div class="m_6a03f287 mantine-Alert-title"><span id="mantine-_R_remqrdub_-title" class="m_698f4f23 mantine-Alert-label">Полный доступ к материалам</span></div><div id="mantine-_R_remqrdub_-body" class="m_7fa78076 mantine-Alert-message"><div style="--group-gap:var(--mantine-spacing-md);--group-align:center;--group-justify:space-between;--group-wrap:wrap" class="m_4081bf90 mantine-Group-root"><p class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Зарегистрируйтесь и получите доступ к этому и десяткам других курсов</p><a style="--button-height:var(--button-height-xs);--button-padding-x:var(--button-padding-x-xs);--button-fz:var(--mantine-font-size-xs);--button-bg:linear-gradient(45deg, var(--mantine-color-blue-filled) 0%, var(--mantine-color-cyan-filled) 100%);--button-hover:linear-gradient(45deg, var(--mantine-color-blue-filled) 0%, var(--mantine-color-cyan-filled) 100%);--button-color:var(--mantine-color-white);--button-bd:none" class="mantine-focus-auto mantine-active m_77c9d27d mantine-Button-root m_87cf2631 mantine-UnstyledButton-root" data-variant="gradient" data-size="xs" href="/u/new"><span class="m_80f1301b mantine-Button-inner"><span class="m_811560b9 mantine-Button-label">Зарегистрироваться</span></span></a></div></div></div></div></div><div class="paywalled m_d08caa0 mantine-Typography-root"><p>Ранее в курсе мы уже познакомились со сбалансированными деревьями поиска — это АВЛ-деревья или красно-черные деревья.</p>
<p>Они способны организовать эффективный поиск элементов за время <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">logN</code>. Но чтобы совершить этот поиск, потребуется выполнить <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">logN</code> операций. Со временем число данных, которые нужно хранить в дереве, будет расти. Дерево потребуется сохранять на более дешевых хранилищах данных вроде жестких дисков, а не хранить в оперативной памяти.</p>
<p>Это ведет к тому, что для поиска элемента в дереве нам придется <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">logN</code> раз обратиться к жесткому диску. При больших <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">N</code> это число операций остается существенным. Операции над жестким диском гораздо медленнее, чем над оперативной памятью. Значит, оборудование будет быстро изнашиваться, а само приложение будет работать медленнее.</p>
<p>Ученым предстояло решить, как организовать эффективный поиск в древовидных структурах, которые должны храниться в постоянной памяти. Чтобы решить эту задачу, они придумали новый вид деревьев — сильноветвящиеся B-деревья и их производные: B+ деревья, B*-деревья, 2-3 деревья.</p>
<p>В этом уроке мы детально познакомимся с видами сильноветвящихся деревьев и особенностями реализации операций поиска, вставки и удаления узлов.</p>
<h2 id="heading-2-1">Устройство B-деревьев</h2>
<p>Рассмотрим дерево, которое состоит из миллиона элементов. Если хранить данные в сбалансированном бинарном дереве поиска, то поиск элемента займет двадцать операций:</p>
<p><code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">log2(1000000) = 19,932</code></p>
<p>Если разбить дерево на страницы, в каждой из которых будет по семь узлов дерева, поиск поддерева с нужным элементом будет выполнен за семь обращений к диску:</p>
<p><code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">log(7+1) 1000000 = 6,644</code></p>
<p>Рассмотрим пример такого разбиения:</p>
<p><img style="--image-object-fit:contain;width:auto" class="m_9e117634 mantine-Image-root" src="/rails/active_storage/blobs/proxy/eyJfcmFpbHMiOnsiZGF0YSI6MTQzMTAsInB1ciI6ImJsb2JfaWQifX0=--bf41ab669b4c6af5ed0cd3763901e5cd93eda1b7/02.png" alt="02" loading="lazy"/></p>
<p>Такая группировка узлов на страницах превращает бинарное дерево в октарное — с восемью дочерними узлами. Число дочерних узлов у страницы может и дальше увеличиваться, например, до 128 элементов. Это приведет к тому, что поиск элемента будет выполнен всего за три обращения к диску:</p>
<p><code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">log128(1000000) = 2,847</code></p>
<p>Таким образом, нам достаточно выбрать оптимальный размер страницы, который удовлетворяет нашим ограничениям по оперативной памяти. Также мы можем хранить в оперативной памяти ссылку на корневой элемент дерева, а сам вид дерева можно привести к виду на рисунке:</p>
<p><img style="--image-object-fit:contain;width:auto" class="m_9e117634 mantine-Image-root" src="/rails/active_storage/blobs/proxy/eyJfcmFpbHMiOnsiZGF0YSI6MTQzMTEsInB1ciI6ImJsb2JfaWQifX0=--836edc1e92d78e8494b68a2ad8ae13b0abf81000/03.png" alt="03" loading="lazy"/></p>
<p>В этом случае в узлах располагается несколько ключей в порядке возрастания слева направо. Дочерние узлы содержат ключи, которые находятся в промежутке между значениями родительского узла.</p>
<p>Помимо особенности расположения ключей стоит отметить, что B-дерево со степенью <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">m</code> обладает следующими свойствами:</p>
<ul>
<li>Глубина всех листьев одинакова</li>
<li>Каждый узел имеет не более <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">m</code> потомков</li>
<li>Каждый узел кроме корневого и листовых имеют не менее <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">m/2</code> потомков</li>
<li>Если высота дерева больше единицы, то у корневого узла не менее двух дочерних узлов</li>
<li>Нелистовой узел с <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">k</code> потомками имеет <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">k-1</code> ключей</li>
</ul>
<p>Представим узел B-дерева в виде кода на JavaScript:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">class BTreeNode {
constructor(value, parent) {
this.leaf = false // Флаг, который показывает, что текущий узел является листовым
this.keys = [value] // Массив ключей (полезной нагрузки) узла
this.parent = parent // Cсылка на родителя
this.children = [] // Массив дочерних узлов
}
}</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Над B-деревьями выполняются все классические операции:</p>
<ul>
<li>Поиск узла</li>
<li>Добавление узла</li>
<li>Удаление узла</li>
</ul>
<p>Однако сложная организация ветвления узлов вносит свои реализации. Далее рассмотрим эти операции подробнее.</p>
<h2 id="heading-2-2">Операции над B-деревьями</h2>
<p>Поиск узлов в случае работы с B-деревом отличается от аналогичной операции над бинарным деревом только порядком действий во время проверки ключей узла. Он будет выглядеть следующим образом:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">class BTreeNode {
// ...
findNode(value) {
let node = this
while (node) { // Проходимся по всем узлам
for (let i = 0; i < node.keys.length; i++) { // Проверяем ключи
if (value === node.keys[i]) {
return node
}
if (value < node.keys[i]) {
if (!node.leaf) {
if (i < node.children.length) {
node = node.children[i]
}
else {
return null
}
break
}
else {
return null
}
}
else if (i === node.keys.length - 1 && !node.leaf) {
if (i + 1 < node.children.length) {
node = node.children[i + 1]
}
else {
return null
}
break
}
}
}
return null
}
}</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>В этом примере можно заметить пересечение с логикой поиска в бинарном дереве поиска. Если искомое значение меньше текущего значения узла, мы переходим по левой от него ветке. Если больше всех ключей узла — переходим на правое поддерево.</p>
<p>Вставка новых элементов в B-дерево разрешается только в листовые узлы. Это приводит к необходимости следить за заполненностью узлов. Если при вставке превысилась максимальная степень узла, то узел нужно разделять на части.</p>
<p>Чтобы разделить узел, создается два новых листовых узла, которые содержат половину значений из существующего узла, и переносится среднее значение в родительский узел.</p>
<p>Если заполнен и корневой узел, то мы разбиваем его на два новых: выбираем среднее значение, создаем для него новый узел, который станет новым корнем всего дерева:</p>
<p><img style="--image-object-fit:contain;width:auto" class="m_9e117634 mantine-Image-root" src="/rails/active_storage/blobs/proxy/eyJfcmFpbHMiOnsiZGF0YSI6MTQzMTIsInB1ciI6ImJsb2JfaWQifX0=--766b86ffbe299fe922c22eb527239a8da7ed9ffc/01.png" alt="01" loading="lazy"/></p>
<p>В данном примере мы вставляем ключ 3 в дерево с одним заполненным корневым узлом. Вставка ключа приводит к переполнению корневого узла. Чтобы решить эту ситуацию, мы разбиваем корневой узел на две части, создаем новый узел со средним значением и делаем его корнем всего дерева.</p>
<p>Аналогично изменение структуры узлов может возникнуть, когда узел удаляется. Если в соседних узлах слишком мало ключей — занятость узлов падает ниже значения <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">m/2</code> — и эти узлы находятся на одном родственном уровне, то такие узлы необходимо слить. Данная ситуация называется <strong>антипереполнением</strong>.</p>
<p>Существует два способа объединения узлов:</p>
<ul>
<li>Если у двух смежных узлов общий предок, и их содержимые помещаются в один узел, их следует объединить</li>
<li>Если содержимое смежных узлов не помещается в одном узле, то ключи перераспределяются между ними, чтобы восстановить баланс</li>
</ul>
<p>Операции слияния и расщепления достаточно дорогостоящие. Чтобы оптимизировать данный процесс, были придуманы специальные подвиды B-деревьев.</p>
<h2 id="heading-2-3">Производные виды деревьев</h2>
<p>К производным видам B-деревьев чаще всего относят следующие три вида:</p>
<ul>
<li>B⁺-деревья</li>
<li>B*-деревья</li>
<li>2-3-деревья</li>
</ul>
<h3 id="heading-3-4">B⁺-деревья</h3>
<p>В B⁺-деревьях данные ключей хранятся только в листовых узлах, а в промежуточных хранятся копии значений ключей. Это помогает эффективно организовывать поиск в блочных средах хранения. Например, в файловых системах, где B⁺-деревья применяют, чтобы хранить каталоги.</p>
<p>Также реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle, поддерживают этот тип деревьев, чтобы организовывать табличные индексы.</p>
<h3 id="heading-3-5">B*-деревья</h3>
<p>B*-дерево ориентировано на более плотное хранение ключей во внутренних узлах. Этот вариант гарантирует, что некорневые узлы заполнены как минимум на две трети от <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">m</code> вместо половины от <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">m</code>.</p>
<p>B*-деревья используются для того, чтобы вызывать дорогостоящую операцию разделения как можно реже. Чтобы достичь этого, вместо немедленного разделения узла при его заполнении, его ключи «переливаются» в соседний узел. Если же и соседний узел заполнен, то ключи приблизительно поровну разделяются на три новых узла.</p>
<h3 id="heading-3-6">2-3-деревья</h3>
<p>2-3 деревья — частный случай B⁺-деревьев с сокращенным количеством элементов на страницах. Каждый узел 2-3-дерева, кроме листовых, может содержать только один ключ и два потомка, либо два ключа и три потомка.</p>
<h2 id="heading-2-7">Выводы</h2>
<p>Способ хранения деревьев может оказывать существенное влияние на организацию структуры узлов и входящих в них ключей. Например, хранение классических бинарных деревьев поиска на жестком диске может привести к многократному росту числа операций над диском.</p>
<p>Для оптимизации хранения и поиска данных в таких условиях были предложены B-деревья. Они помогают сократить нагрузку на диск. Это возможно, если увеличить количество веток в узлах и хранить несколько ключей полезной нагрузки.</p></div><div style="margin-block:var(--mantine-spacing-xl)" class=""><h2 style="--title-fw:var(--mantine-h2-font-weight);--title-lh:var(--mantine-h2-line-height);--title-fz:var(--mantine-h2-font-size);margin-bottom:var(--mantine-spacing-md)" class="m_8a5d1357 mantine-Title-root" data-order="2">Рекомендуемые программы</h2><style data-mantine-styles="inline">.__m__-_R_2mremqrdub_{--carousel-slide-gap:var(--mantine-spacing-xs);--carousel-slide-size:70%;}@media(min-width: 36em){.__m__-_R_2mremqrdub_{--carousel-slide-gap:var(--mantine-spacing-xl);--carousel-slide-size:50%;}}</style><div style="--carousel-control-size:calc(2.5rem * var(--mantine-scale));--carousel-controls-offset:var(--mantine-spacing-sm);margin-bottom:var(--mantine-spacing-lg);padding-block:var(--mantine-spacing-sm);background:var(--app-color-surface)" class="m_17884d0f mantine-Carousel-root responsiveClassName" data-orientation="horizontal" data-include-gap-in-size="true"><div class="m_39bc3463 mantine-Carousel-controls" data-orientation="horizontal"><button class="mantine-focus-auto m_64f58e10 mantine-Carousel-control m_87cf2631 mantine-UnstyledButton-root" type="button" data-inactive="true" data-type="previous" tabindex="-1"><svg viewBox="0 0 15 15" fill="none" xmlns="http://www.w3.org/2000/svg" style="transform:rotate(90deg);width:calc(1rem * var(--mantine-scale));height:calc(1rem * var(--mantine-scale));display:block"><path d="M3.13523 6.15803C3.3241 5.95657 3.64052 5.94637 3.84197 6.13523L7.5 9.56464L11.158 6.13523C11.3595 5.94637 11.6759 5.95657 11.8648 6.15803C12.0536 6.35949 12.0434 6.67591 11.842 6.86477L7.84197 10.6148C7.64964 10.7951 7.35036 10.7951 7.15803 10.6148L3.15803 6.86477C2.95657 6.67591 2.94637 6.35949 3.13523 6.15803Z" fill="currentColor" fill-rule="evenodd" clip-rule="evenodd"></path></svg></button><button class="mantine-focus-auto m_64f58e10 mantine-Carousel-control m_87cf2631 mantine-UnstyledButton-root" type="button" data-inactive="true" data-type="next" tabindex="-1"><svg viewBox="0 0 15 15" fill="none" xmlns="http://www.w3.org/2000/svg" style="transform:rotate(-90deg);width:calc(1rem * var(--mantine-scale));height:calc(1rem * var(--mantine-scale));display:block"><path d="M3.13523 6.15803C3.3241 5.95657 3.64052 5.94637 3.84197 6.13523L7.5 9.56464L11.158 6.13523C11.3595 5.94637 11.6759 5.95657 11.8648 6.15803C12.0536 6.35949 12.0434 6.67591 11.842 6.86477L7.84197 10.6148C7.64964 10.7951 7.35036 10.7951 7.15803 10.6148L3.15803 6.86477C2.95657 6.67591 2.94637 6.35949 3.13523 6.15803Z" fill="currentColor" fill-rule="evenodd" clip-rule="evenodd"></path></svg></button></div><div class="m_a2dae653 mantine-Carousel-viewport" data-type="media"><div class="m_fcd81474 mantine-Carousel-container __m__-_R_2mremqrdub_" data-orientation="horizontal"><div class="m_d98df724 mantine-Carousel-slide" data-orientation="horizontal"><div tabindex="0" style="cursor:pointer;height:100%"><a style="text-decoration:none" class="mantine-focus-auto m_849cf0da m_b6d8b162 mantine-Text-root mantine-Anchor-root" data-underline="hover" href="/programs/algorithms?promo_name=programs_list&promo_position=course&promo_creative=catalog_card&promo_type=card" target="_blank"><div style="height:100%" class="m_e615b15f mantine-Card-root m_1b7284a3 mantine-Paper-root" data-with-border="true"><div style="--group-gap:calc(0.25rem * var(--mantine-scale));--group-align:center;--group-justify:flex-start;--group-wrap:nowrap" class="m_4081bf90 mantine-Group-root"><span style="font-size:var(--mantine-font-size-sm)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">2 месяца</span><span class="mantine-focus-auto m_b6d8b162 mantine-Text-root">·</span><span style="font-size:var(--mantine-font-size-sm)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Для продвинутых</span></div><p style="margin-bottom:var(--mantine-spacing-sm);font-size:var(--mantine-font-size-h5);font-weight:bold" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Алгоритмы и структуры данных</p><p class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Алгоритмы для собеседований</p><div style="margin-top:auto" class=""><div class="m_4451eb3a mantine-Center-root"><img style="opacity:0.8;width:70%" class="m_9e117634 mantine-Image-root mantine-visible-from-xs" src="https://hexlet.io/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6NDAyOCwicHVyIjoiYmxvYl9pZCJ9fQ==--ae9eed98663dd1201759d042a5ba7ca790866156/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJ3ZWJwIiwicmVzaXplX3RvX2xpbWl0IjpbNDAwLDQwMF0sInNhdmVyIjp7InF1YWxpdHkiOjg1fX0sInB1ciI6InZhcmlhdGlvbiJ9fQ==--5b6f46dacd1af664f27558553a58076185091823/Programming-bro.png" alt="Алгоритмы и структуры данных" loading="eager"/></div><div style="--group-gap:var(--mantine-spacing-md);--group-align:end;--group-justify:space-between;--group-wrap:wrap;margin-top:var(--mantine-spacing-xs)" class="m_4081bf90 mantine-Group-root"><p style="font-size:var(--mantine-font-size-xl)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">от 3 900 ₽</p><p style="font-size:var(--mantine-font-size-sm)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Посмотреть →</p></div></div></div></a></div></div><div class="m_d98df724 mantine-Carousel-slide" data-orientation="horizontal"><div tabindex="0" style="cursor:pointer;height:100%"><a style="text-decoration:none" class="mantine-focus-auto m_849cf0da m_b6d8b162 mantine-Text-root mantine-Anchor-root" data-underline="hover" href="/courses?promo_name=programs_list&promo_position=course&promo_creative=catalog_card&promo_type=card"><div style="height:100%" class="m_e615b15f mantine-Card-root m_1b7284a3 mantine-Paper-root" data-with-border="true"><h2 style="--title-fw:var(--mantine-h2-font-weight);--title-lh:var(--mantine-h2-line-height);--title-fz:var(--mantine-h2-font-size);margin-bottom:var(--mantine-spacing-md);font-size:var(--mantine-font-size-h3)" class="m_8a5d1357 mantine-Title-root" data-order="2" data-responsive="true">Каталог</h2><p style="margin-bottom:auto" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Полный список доступных курсов по разным направлениям</p><div style="margin-top:auto" class=""><div class="m_4451eb3a mantine-Center-root"><img style="opacity:0.8;width:70%" class="m_9e117634 mantine-Image-root mantine-visible-from-xs" src="/vite/assets/development-BVihs_d5.png" alt="Orientation"/></div></div></div></a></div></div></div></div></div></div></div></div></div><style data-mantine-styles="inline">.__m__-_R_1bdub_{--col-flex-grow:auto;--col-flex-basis:8.333333333333334%;--col-max-width:8.333333333333334%;}@media(min-width: 48em){.__m__-_R_1bdub_{--col-flex-grow:auto;--col-flex-basis:16.666666666666668%;--col-max-width:16.666666666666668%;}}</style><div style="min-width:0rem;height:100%;min-height:0rem" class="m_96bdd299 mantine-Grid-col __m__-_R_1bdub_"><div style="margin-inline:var(--mantine-spacing-xs)" class="mantine-visible-from-sm"><a style="--button-color:var(--mantine-color-white);margin-bottom:var(--mantine-spacing-lg);text-decoration:none" class="mantine-focus-auto m_849cf0da mantine-focus-auto m_77c9d27d mantine-Button-root m_87cf2631 mantine-UnstyledButton-root m_b6d8b162 mantine-Text-root mantine-Anchor-root" data-underline="hover" href="/courses/algorithms-trees/lessons/btrees/finish_unit?unit=theory" data-disabled="true" data-block="true" disabled=""><span class="m_80f1301b mantine-Button-inner"><span class="m_811560b9 mantine-Button-label"><span style="margin-inline-end:var(--mantine-spacing-xs)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Дальше</span>→</span></span></a><a style="padding-inline:0rem" class="mantine-focus-auto m_f0824112 mantine-NavLink-root m_87cf2631 mantine-UnstyledButton-root"><span class="m_690090b5 mantine-NavLink-section" data-position="left"><div style="--ti-size:var(--ti-size-sm);--ti-bg:transparent;--ti-color:var(--mantine-color-indigo-light-color);--ti-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;color:inherit" class="m_7341320d mantine-ThemeIcon-root" data-variant="transparent" data-size="sm"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="1.2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-list-numbers "><path d="M11 6h9"></path><path d="M11 12h9"></path><path d="M12 18h8"></path><path d="M4 16a2 2 0 1 1 4 0c0 .591 -.5 1 -1 1.5l-3 2.5h4"></path><path d="M6 10v-6l-2 2"></path></svg></div></span><div class="m_f07af9d2 mantine-NavLink-body"><span class="m_1f6ac4c4 mantine-NavLink-label">Навигация по теме</span><span class="m_57492dcc mantine-NavLink-description">Теория</span></div><span class="m_690090b5 mantine-NavLink-section" data-position="right"></span></a><div style="margin-block:var(--mantine-spacing-lg)" class="m_3eebeb36 mantine-Divider-root" data-orientation="horizontal" role="separator"></div><div style="margin-block:var(--mantine-spacing-lg)" class=""><div style="justify-content:space-between;margin-bottom:calc(0.1875rem * var(--mantine-scale));color:var(--mantine-color-dimmed);font-size:var(--mantine-font-size-xs)" class="m_8bffd616 mantine-Flex-root __m__-_R_qimrbdub_"><p style="font-size:var(--mantine-font-size-xs)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Завершено</p><p style="font-size:var(--mantine-font-size-xs)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">0 / 8</p></div><div style="--progress-size:var(--progress-size-sm)" class="m_db6d6462 mantine-Progress-root" data-size="sm"><div style="--progress-section-size:0%;--progress-section-color:var(--mantine-color-gray-filled)" class="m_2242eb65 mantine-Progress-section" role="progressbar" aria-valuemax="100" aria-valuemin="0" aria-valuenow="0" aria-valuetext="0%"></div></div></div><button style="padding-inline:0rem" class="mantine-focus-auto m_f0824112 mantine-NavLink-root m_87cf2631 mantine-UnstyledButton-root" type="button"><span class="m_690090b5 mantine-NavLink-section" data-position="left"><div style="--ti-size:var(--ti-size-sm);--ti-bg:transparent;--ti-color:var(--mantine-color-indigo-light-color);--ti-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;color:inherit" class="m_7341320d mantine-ThemeIcon-root" data-variant="transparent" data-size="sm"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="1.2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-message "><path d="M8 9h8"></path><path d="M8 13h6"></path><path d="M18 4a3 3 0 0 1 3 3v8a3 3 0 0 1 -3 3h-5l-5 3v-3h-2a3 3 0 0 1 -3 -3v-8a3 3 0 0 1 3 -3h12"></path></svg></div></span><div class="m_f07af9d2 mantine-NavLink-body"><span class="m_1f6ac4c4 mantine-NavLink-label">Обсуждения (архив)</span><span class="m_57492dcc mantine-NavLink-description"></span></div></button><div style="--toc-bg:var(--mantine-color-blue-light);--toc-color:var(--mantine-color-blue-light-color);--toc-size:var(--mantine-font-size-sm);--toc-radius:var(--mantine-radius-sm);margin-top:var(--mantine-spacing-xl)" class="m_bcaa9990 mantine-TableOfContents-root" data-variant="light" data-size="sm"></div></div><div class="mantine-hidden-from-sm"><div style="--stack-gap:0rem;--stack-align:stretch;--stack-justify:flex-start" class="m_6d731127 mantine-Stack-root"><a style="--button-color:var(--mantine-color-white);margin-bottom:var(--mantine-spacing-xs);padding:0rem;text-decoration:none" class="mantine-focus-auto m_849cf0da mantine-focus-auto m_77c9d27d mantine-Button-root m_87cf2631 mantine-UnstyledButton-root m_b6d8b162 mantine-Text-root mantine-Anchor-root" data-underline="hover" href="/courses/algorithms-trees/lessons/btrees/finish_unit?unit=theory" data-disabled="true" data-block="true" disabled=""><span class="m_80f1301b mantine-Button-inner"><span class="m_811560b9 mantine-Button-label">→</span></span></a><button style="--ai-size:var(--ai-size-sm);--ai-bg:transparent;--ai-hover:var(--mantine-color-indigo-light-hover);--ai-color:var(--mantine-color-indigo-light-color);--ai-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;padding-block:var(--mantine-spacing-lg);color:inherit;width:100%" class="mantine-focus-auto m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="subtle" data-size="sm" data-disabled="true" type="button" disabled=""><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="1.2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-list-numbers "><path d="M11 6h9"></path><path d="M11 12h9"></path><path d="M12 18h8"></path><path d="M4 16a2 2 0 1 1 4 0c0 .591 -.5 1 -1 1.5l-3 2.5h4"></path><path d="M6 10v-6l-2 2"></path></svg></span></button><button style="--ai-size:var(--ai-size-sm);--ai-bg:transparent;--ai-hover:var(--mantine-color-indigo-light-hover);--ai-color:var(--mantine-color-indigo-light-color);--ai-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;padding-block:var(--mantine-spacing-lg);color:inherit;width:100%" class="mantine-focus-auto mantine-active m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="subtle" data-size="sm" type="button"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="1.2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-message "><path d="M8 9h8"></path><path d="M8 13h6"></path><path d="M18 4a3 3 0 0 1 3 3v8a3 3 0 0 1 -3 3h-5l-5 3v-3h-2a3 3 0 0 1 -3 -3v-8a3 3 0 0 1 3 -3h12"></path></svg></span></button></div></div></div></div></div></div></div>
</main>
<footer class="bg-dark fw-light text-light px-3 py-5">
<div class="row small">
<div class="col-12 col-sm-6 col-md-3">
<div class="h5 mb-3">Хекслет</div>
<ul class="list-unstyled">
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/about">О нас</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/testimonials">Отзывы</a>
</li>
<li>
<span class="nav-link link-light py-1 ps-0 external-link" data-href="https://b2b.hexlet.io" role="button">Корпоративное обучение</span>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/blog">Блог</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/qna">Вопросы и ответы</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/glossary">Глоссарий</a>
</li>
<li>
<span class="nav-link link-light py-1 ps-0 external-link" data-href="https://help.hexlet.io" data-target="_blank" role="button">Справка</span>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" target="_blank" rel="noopener noreferrer" href="/map">Карта сайта</a>
</li>
</ul>
</div>
<div class="col-12 col-sm-6 col-md-3">
<div class="h5 fw-normal mb-3">Направления</div>
<ul class="list-unstyled">
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_devops">DevOps
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_data_analytics">Аналитика
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_backend_development">Бэкенд
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_programming">Программирование
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_testing">Тестирование
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_front_end_dev">Фронтенд
</a></li>
</ul>
</div>
<div class="col-12 col-sm-6 col-md-3">
<div class="h5">Профессии</div>
<ul class="list-unstyled">
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/devops-engineer-from-scratch">DevOps-инженер с нуля</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/go">Go-разработчик</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/java">Java-разработчик</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/python">Python-разработчик </a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/data-analytics">Аналитик данных</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/qa-engineer">Инженер по ручному тестированию</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/php">РНР-разработчик</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/frontend">Фронтенд-разработчик</a>
</li>
</ul>
</div>
<div class="col-12 col-sm-6 col-md-3">
<div class="h5">Навыки</div>
<ul class="list-unstyled">
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/python-django-developer">Django</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/docker">Docker</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/php-laravel-developer">Laravel</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/postman">Postman</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/js-react-developer">React</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/js-rest-api">REST API в Node.js</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/spring-boot">Spring Boot</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/typescript">Typescript</a>
</li>
</ul>
</div>
</div>
<hr>
<div class="row">
<div class="col-12 col-sm-4 col-md-2">
<div class="fs-4">
<ul class="list-unstyled d-flex">
<li class="me-3">
<a aria-label="Telegram" target="_blank" class="link-light" rel="noopener noreferrer nofollow" href="https://t.me/hexlet_ru"><span class="bi bi-telegram"></span>
</a></li>
<li>
<a aria-label="Youtube" target="_blank" class="link-light" rel="noopener noreferrer nofollow" href="https://www.youtube.com/user/HexletUniversity"><span class="bi bi-youtube"></span>
</a></li>
</ul>
</div>
<div class="mb-2 d-flex flex-column">
<a class="link-light text-decoration-none" rel="nofollow" href="mailto:support@hexlet.io">support@hexlet.io</a>
<a class="link-light text-decoration-none py-2" target="_blank" href="https://t.me/hexlet_help_bot">t.me/hexlet_help_bot</a>
</div>
<ul class="list-unstyled d-flex">
<li class="me-3">
<span class="link-light text-decoration-none opacity-50 x-font-size-18 external-link" rel="nofollow" data-href="https://hexlet.io/locale/switch?new_locale=en" data-target="_self" role="button"><span class="my-auto">EN</span>
</span></li>
<li class="me-3">
<span class="link-light text-decoration-none opacity-50 x-font-size-18 opacity-100 external-link" rel="nofollow" data-href="https://ru.hexlet.io/locale/switch?new_locale=ru" data-target="_self" role="button"><span class="my-auto">RU</span>
</span></li>
<li class="me-3">
<span class="link-light text-decoration-none opacity-50 x-font-size-18 external-link" rel="nofollow" data-href="https://kz.hexlet.io/locale/switch?new_locale=kz" data-target="_self" role="button"><span class="my-auto">KZ</span>
</span></li>
</ul>
</div>
<div class="col-12 col-sm-4 col-md-3">
<ul class="list-unstyled fs-4">
<li class="mb-3">
<a class="link-light text-decoration-none" href="tel:8%20800%20100%2022%2047">8 800 100 22 47</a>
<span class="d-block opacity-50 small">бесплатно по РФ</span>
</li>
<li>
<a class="link-light text-decoration-none" href="tel:%2B7%20495%20085%2021%2062">+7 495 085 21 62</a>
<span class="d-block opacity-50 small">бесплатно по Москве</span>
</li>
</ul>
</div>
<div class="col-12 col-sm-4 col-md-3">
<div class="small mb-3">Образовательные услуги оказываются на основании Л035-01298-77/01989008 от 14.03.2025</div>
<ul class="list-unstyled small">
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/legal">Правовая информация</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/offer">Оферта</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/license">Лицензия</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/contacts">Контакты</a>
</li>
</ul>
</div>
<div class="col-12 col-sm-12 col-md-4 small">
<div class="mb-2">
<div>ООО «<a href="/" class="text-decoration-none link-light">Хекслет Рус</a>»</div>
<div>108813 г. Москва, вн.тер.г. поселение Московский,</div>
<div>г. Московский, ул. Солнечная, д. 3А, стр. 1, помещ. 20Б/3</div>
<div>ОГРН 1217300010476</div>
<div>ИНН 7325174845</div>
</div>
<hr>
<div>АНО ДПО «<a href="/" class="text-decoration-none link-light">Учебный центр «Хекслет</a>»</div>
<div>119331 г. Москва, вн. тер. г. муниципальный округ</div>
<div>Ломоносовский, пр-кт Вернадского, д. 29</div>
<div>ОГРН 1247700712390</div>
<div>ИНН 7736364948</div>
</div>
</div>
</footer>
<div id="root-assistant-offcanvas"></div>
<script src="/vite/assets/assistant-Bukl1lYy.js" crossorigin="anonymous" type="module"></script><link rel="modulepreload" href="/vite/assets/chunk-DsPFFUou.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/init-BrRXra1y.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/ErrorFallbackBlock-naDSYSy9.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/MarkdownBlock-DbyKWoR_.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/gon-D3e4yh1x.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/mantine-CGMYrt2Y.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/shiki-V011pkdv.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/utils-DRqSHbQE.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/routes-CCH8ilKF.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/lib-XR8Qr8kR.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/dist-GCHh59xr.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Box-B5-OOzBf.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/notifications.store-C-3AFSMn.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/useIsomorphicEffect-HJ6VK0D3.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/lib-KSp6QbZ0.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/axios-BEvgo0ym.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/classnames-l6ipYlLR.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/dayjs.min-BkKovM-s.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/debounce-jMQ_Cf4f.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/i18next-BlSq9s7B.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/client-U9M77rxp.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/react-dom-DaLxUz_h.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/useTranslation-Bx1Cdrkz.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/compiler-runtime-6XxiPFnt.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/jsx-runtime-CwjcCKJi.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/react-CkL4ZRHB.js" as="script" crossorigin="anonymous">
<script defer src="https://static.cloudflareinsights.com/beacon.min.js/v67327c56f0bb4ef8b305cae61679db8f1769101564043" integrity="sha512-rdcWY47ByXd76cbCFzznIcEaCN71jqkWBBqlwhF1SY7KubdLKZiEGeP7AyieKZlGP9hbY/MhGrwXzJC/HulNyg==" data-cf-beacon='{"version":"2024.11.0","token":"d11015b65d11429ea6b4a2ef37dd7e0b","server_timing":{"name":{"cfCacheStatus":true,"cfEdge":true,"cfExtPri":true,"cfL4":true,"cfOrigin":true,"cfSpeedBrain":true},"location_startswith":null}}' crossorigin="anonymous"></script>
</body>
</html>