Глубокое понимание базовой реализации и характеристик таблицы пропуска Redis.

Ставьте лайк и смотрите снова, вырабатывайте привычку, ищите в паблике [дайм тек] Обратите внимание на более оригинальные технические статьи. эта статьяGitHub org_hejianhui/JavaStudyБыл включен, есть моя серия статей.

предисловие

Здесь мы сначала вспоминаем временную сложность обычных линкеров, вы можете видетьlook upОперация$O(n)$Да, другие операции$O(1)$Временная сложность . То есть, если вам нужно получить доступ к любому элементу в нем случайным образом, его средняя временная сложность равна$O(n)$Да, это проблема связанных списков. Отсюда видно, что так называемой идеальной структуры данных не существует.Если она идеальна, две структуры данных массива или связанного списка не должны сосуществовать, и можно напрямую использовать самую мощную структуру данных. Таким образом, это эквивалентно тому, что у каждого есть свои преимущества и недостатки, в зависимости от того, где находится ваш сценарий использования, в качестве полного сравнения я приведу здесь обе временные сложности.

Временная сложность связанного списка

Временная сложность массива

Уведомление: временная сложность операции добавления массива обычно составляет O(n), но можно выполнить специальную оптимизацию до O(1). Используемый метод состоит в том, чтобы применить немного больший объем памяти, а затем зарезервировать часть пространства в начале массива, а затем операция prepend состоит в перемещении нижнего индекса заголовка вперед на одну позицию.

Пропустить список

Временная сложность двух структур массива и связанного списка была рассмотрена ранее.В одном случае скорость связанного списка$O(n)$Этого будет недостаточно, давайте посмотрим, к чему относится эта ситуация?

Когда элементы связанного списка упорядочены

Внимание относится ко всему элементу, если он упорядочен, в некоторых случаях, например, в базе данных или при запросе некоторых упорядоченных деревьев, даже если он хранится в связанном списке, мы находим его Элементы упорядочены, например, следующий восходящий связанный список,134578910Он расположен в порядке возрастания.В настоящее время нам нужно быстро запросить, например, где находится 9 или появляется ли 5 ​​в этом связанном списке.В это время вы обнаружите, что если вы используете обычные массивы, вы можете выполнить двоичный поиск очень быстро Найдите местоположение 5 и узнайте, существует ли элемент.

Есть упорядоченный массив, поэтому вопрос в том, если он заказывается, но как он должен быть эффективно ускорен в случае связанного списка? Таким образом, примерно в 1990 году в современном времени появилась новая структура данных, его имяПрыжок.

Особенности скип-стола

Уведомление: может использоваться только тогда, когда элементы упорядочены.

Таким образом, список пропуска представляет собой сбалансированное дерево (AVL Tree) и бинарный поиск таблицы, являющийся своего рода вставкой/удалением/поиском.$O(log n)$структура данных. Появился в 1989 году.

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

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

Таблица прыжков (skiplist) представляет собой рандомизированный набор данных Уильяма Пью в статье«Списки пропуска: вероятностная альтернатива сбалансированным деревьям»Предложена таблица перехода в упорядоченном виде для сохранения в иерархическом списке элементов, эффективность и сбалансированное дерево сопоставимы - поиск, удаление, добавление и другие операции могут быть завершены вовремя для следующих нескольких ожиданий и по сравнению с деревом для баланса , таблица прыжков стала намного проще и интуитивно понятнее.

Как ускорить упорядоченный связанный список

Предположим, что имеется упорядоченный связанный список, примитивный связанный список, такой как 1 3 4 5 7 8 9 10. Его запрос временной сложности определенно$O(n)$Да, тогда спросите, как оптимизировать? Как сделать простую оптимизацию? Он может снизить сложность времени запроса, то есть ускорить его.

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

• Временная сложность: запрос O (n)
• Простая оптимизация: добавьте указатели на начало и конец

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

Добавьте индекс первого уровня

Как повысить эффективность линейного поиска в связном списке?В частности, давайте посмотрим на рисунок выше. В случае исходного связанного списка мы добавляем еще одно измерение, то есть добавляем еще один слой индекса на него. Мы называем его индексом первого уровня. Тогда индекс первого уровня делает не указывает на следующий элемент своего элемента element, а указывает на свой следующий next, то есть можно понимать как next+1, поэтому индекс первого уровня это первый элемент, сразу третий элемент, пятый элемент, седьмой элемент элемента.

• Здесь вы найдете, если вы ищете 7, что мы делаем? Мы ищем так, сначала ищем индекс первого уровня, чтобы увидеть, есть ли 1 4 7 , если есть, это означает, что 7 существует в этом связанном списке, что означает, что мы запросили.
• Давайте посмотрим на другой элемент, скажем, 8, как мы пойдем? Или сначала найдите первый уровень, 8 больше 1, поэтому значение индекса 4 достигается позже, 8 больше 4, 7 больше 7, а 8 тоже больше 7, а затем продолжайте находить, что 9 больше 8 . Объясните, что 8 существует в элементе между двумя индексами 7 и 9, тогда в это время от элемента первого уровня до исходного связанного списка вы обнаружите, что 8 найдено путем поиска с соответствующей позиции один за другим, указывая, что 8 также существует.

Добавить индекс второго уровня

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

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

• Например, если я хочу найти 8, например, сначала найдите 1, 8 больше, чем 1, а затем найдите 7. В это время вы обнаружите, что 8 также больше, чем 7, а затем найдите его. , предполагая, что элемент после этого элемента равен 11 или 12. В это время вы обнаружите, что 8 меньше, чем элемент за ним, поэтому, если 7 здесь, вы должны спуститься на один уровень индекса, перейти к 7 из первый уровень индекса, а затем аналогично предыдущему между 7 и 9, а затем перейти к 8 и продолжать идти вниз.

Добавить многоуровневый индекс

И так далее, увеличивать многоуровневый индекс

Предположим, есть такой исходный связанный список с пятиуровневым индексом, тогда нам нужно проверить элемент, например, чтобы проверить 62 элемента или промежуточных элементов, что аналогично рисунку ниже, спускаемся на один уровень вниз, а потом можно в конце проверить до нужного нам 62 элемента. Конечно, если вы, наконец, найдете исходный связанный список, вы обнаружите, что, например, мы хотим проверить 63 или 61. Если в исходном связанном списке нет элемента, мы говорим, что элемент не существует. упорядоченный связанный список, то есть в списке с пропусками.Если такой элемент не может быть найден, такой вывод можно сделать и в конце.

Временная сложность анализа запросов таблицы переходов

Расчет временной сложности таблицы пропуска

• n/2, n/4, n/8, количество узлов индекса k-го уровня равно n/(2^k)

• Предположим, индекс имеет уровень h, а индекс самого высокого уровня имеет 2 узла. n/(2^h) = 2, поэтому h = log2(n)-1

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

Общее количество элементов, которые необходимо пройти в каждом слое, равно 3, поэтому log28 здесь — это его временная сложность. Последнее слово доказано: временная сложность log2n. То есть из простейшего исходного связанного списка его временная сложность O(n) уменьшается до log2n временной сложности. Это уже большое улучшение. Предполагая, что это 1024, вы обнаружите, что исходный связанный список нужно проверить 1024 раза, чтобы наконец получить этот элемент, поэтому здесь вам нужно только проверить (2 в 10-й степени — 1024 раза) порядка десяти раз. .

Форма недвижимости

На самом деле мы используем таблицу прыжков в случае, которая связана с добавлением и удалением этого элемента, который привел к его индексу, то некоторые из него не совсем очень аккуратно, и, наконец, после нескольких изменений, некоторые из которых последний индекс, где будет Пересекайте несколько, он будет меньше в некоторых местах только в нескольких шагах, потому что некоторые элементы, которые будут добавлены и удалены, и его затраты на обслуживание относительно высоки, также сказали, что при добавлении элемента вы поместите его для обновления индекса Опять же, вы хотите удалить элемент, также необходимо снова обновить свой индекс. В этом процессе добавьте и удалите его, тогда становится сложность времени$O(logn)$.

Средняя временная сложность запроса произвольных данных в таблице пропусков составляет O(logn)..

Анализ пространственной сложности запроса Skip Table

Здесь мы предполагаем, что его длина равна n, а затем, согласно предыдущему примеру, если каждые два узла рисуются для создания индекса, то его индекс первого уровня равен n половине, правильно. Наконец, следующим образом:

• Размер исходного связанного списка равен n, и на каждые 2 узла выводится 1 узел. Количество узлов в каждом слое индекса:  $\frac{n}{2},\frac{n}{4},\frac{n}{8}...,8,4,2$

• Размер исходного связанного списка равен n, и 1 рисуется для каждых 3 узлов, а количество узлов в каждом индексе равно:$\frac{n}{3},\frac{n}{9},\frac{n}{27}...,9,3,1$

• Сложность пространства$O(n)$

Состав скипового стола

Ниже приведен пример типичного счетчика прыжков:Как видно из рисунка, таблица прыжков в основном состоит из следующих частей:

• Голова: Указатель узла, отвечающий за поддержку таблицы переходов.
• Узел таблицы переходов: содержит значения элементов, а также несколько слоев.
• Слой: содержит указатели на другие элементы. Количество элементов, которые пересекает высокоуровневый указатель, больше или равно низкоуровневому указателю.Для повышения эффективности поиска программа всегда начинает обращение с высокого уровня, а затем постепенно понижает уровень по мере диапазон значений элементов уменьшен.
• Конец таблицы: все состоит из нулевых, указывающих конец стола прыжка.

Redis реализует таблицу прыжка

Таблица переходов Redis задаетсяredis.h/zskiplistNodeиredis.h/zskiplistДва определения структуры, гдеzskiplistNodeструктуры используются для представления узлов списка пропуска, аzskiplistСтруктура используется для хранения соответствующей информации об узле таблицы переходов, такой как количество узлов, указатели на головной и хвостовой узлы и т. д.На изображении выше показан пример списка пропуска, структура zskiplist в крайнем левом углу изображения, которая содержит следующие свойства:

• header: Указывает на узел заголовка таблицы переходов.
• tail: Указывает на узел нижнего колонтитула таблицы переходов.
• level: Запишите номер слоя узла с наибольшим номером слоя в текущей таблице переходов (номер слоя узла заголовка не учитывается).
• length: Запишите длину таблицы переходов, то есть количество узлов, содержащихся в настоящее время в таблице переходов (узел заголовка не учитывается).

родыzskiplistСправа от конструкции четыреzskiplistNodeструктура, которая содержит следующие свойства:

• Слой (уровень): используется в узлахL1,L2,L3И т. д., чтобы отметить каждый слой узла,L1представляет первый слой,L2представляет второй слой и так далее. Каждый слой имеет два свойства: прямой указатель и диапазон. Прямой указатель используется для доступа к другим узлам в направлении конца списка, а диапазон записывает расстояние между узлом, на который указывает прямой указатель, и текущим узлом. На рисунке выше стрелка с числом в строке представляет собой указатель вперед, а это число — диапазон. Когда программа переходит от головы к хвосту, доступ будет следовать прямому указателю слоя.
• обратный (обратный) указатель: используется в узлахBWСлово отмечает обратный указатель узла, который указывает на предыдущий узел, расположенный в текущем узле. Задний указатель используется, когда программа перемещается от конца таблицы к началу таблицы.
• Score (оценка): в каждом узле1.0,2.0и3.0это оценка, хранящаяся узлом. В таблице переходов узлы располагаются от меньшего к большему в соответствии с их сохраненными очками.
• Объект-член (obj): в каждом узлеo1,o2иo3является объектом-членом, хранимым узлом.

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

пропустить узел таблицы

Реализация узла таблицы пропуска даетсяredis.h/zskiplistNodeОпределение структуры:

typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

Этаж

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

Каждый раз, когда создается новый узел таблицы пропуска, программа следует степенному закону (power law, чем больше число, тем меньше вероятность появления) Произвольно сгенерировать число между1 и 32Значение между какlevelРазмер массива, который является «высотой» слоя.

На рисунке ниже показаны три высоты1Этаж,3слой и5узлы слоя, так как индексы массива в C всегда начинаются с0начинается, поэтому первый уровень узловlevel[0], а второй слойlevel[1], и так далее.

указатель вперед

Каждый слой имеет прямую указатель в направлении конца таблицы (level[i].forwardсвойство), которое используется для доступа к узлам из заголовка в нижний колонтитул.На рисунке выше пунктирной линией показан путь программы, проходящий через все узлы в таблице переходов от головы к хвосту таблицы:

1. Итератор сначала посещает первый узел (заголовок) списка пропуска, затем перемещается от прямого указателя на уровне 4 ко второму узлу в списке.
2. На втором узле программа переходит к третьему узлу в списке по указателю продвижения второго уровня.
3. На третьем узле программа также перемещается к четвертому узлу в списке по указателю продвижения второго уровня.
4. Когда программа снова перемещается по прямому указателю четвертого узла, она сталкивается сNULL, программа знает, что в это время достигнут конец списка пропуска, поэтому она завершает обход.

охватывать

Размах слоя (level[i].spanсвойство) используется для записи расстояния между двумя узлами:

• Чем больше расстояние между двумя узлами, тем дальше они друг от друга.
• направлениеNULLПромежуток всех авансовых указателей0Потому что они не связаны ни с одним узлом.

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

Например, следующее обозначено пунктирной линией, чтобы найти оценку в таблице пропусков как3.0, объект-членo3При узле , по пути встречаются слои: процесс поиска проходит только через один слой, а длина слоя равна3, поэтому ранжирование целевого узла в таблице переходов равно3.

Пример должен быть отмечен пунктирной линией, чтобы найти счет в таблице прыжков.2.0, объект-членo2Слои, возникающие на пути к найденному узлу: В процессе нахождения узла программа проходит через два отрезка пути.1Следовательно, можно подсчитать, что ранг целевого узла в таблице переходов равен 2.

обратный указатель

Задний указатель узла (backwardатрибут) используется для доступа к узлам из конца списка в начало списка: в отличие от прямого указателя, который может пропускать несколько узлов за раз, поскольку каждый узел имеет только один обратный указатель, он может вернуться только к предыдущий узел каждый раз.Вышеуказанная фигура показывает с пунктирными линиями, если все узлы в таблице перехода пересекаются с конца таблицы к головке: программа сначала проходитtailУказатель обращается к хвостовому узлу, затем обращается к предпоследнему узлу через обратный указатель, затем следует обратному указателю для доступа к предпоследнему узлу, а затем встречает указатель наNULLуказатель назад, поэтому доступ заканчивается.

Оценка и членство

• Оценка узла (scoreимущество) представляет собойdoubleЧисло с плавающей запятой, все узлы в таблице переходов отсортированы в порядке возрастания количества очков.
• объект-член узла (objсвойство) является указателем на строковый объект, который содержит значение SDS (простая динамическая строка).

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

Например, в таблице пропусков, показанной на рисунке ниже, все три узла таблицы пропусков имеют одинаковую оценку.10086.0, но сохраняет объект-членo1Узлы помещаются в объект-член сохранения.o2иo3Перед узлом сохранить объекты пользователейo2Узел также оценивается в сохранении объектов-членов.o3Перед узлом видно, чтоo1,o2,o3Порядок трех объектов-членов в словаре следующий:o1 <= o2 <= o3.

стол для прыжков

Хотя только несколько узлов таблицы переходов могут формировать таблицу переходов, как показано на следующем рисунке:Но с помощьюzskiplistструктуру для хранения этих узлов, программа может более удобно обрабатывать всю таблицу переходов, например, быстро получить доступ к узлу заголовка и нижнего колонтитула таблицы переходов или быстро получить количество узлов таблицы переходов (то есть количество узлов таблицы переходов). узлы), длина) и другую информацию, а именно: zskiplistСтруктура определяется следующим образом:

typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

• headerиtailУказатели указывают на узлы заголовка и нижнего колонтитула таблицы переходов соответственно, и с помощью этих двух указателей сложность программы, обнаруживающей узлы верхнего и нижнего колонтитула, составляет O (1).
• используяlengthАтрибуты для записи количества узлов, программа может вернуть длину таблицы переходов в пределах O (1) сложности.
• levelАтрибут используется для получения количества слоев узла с самой высокой высотой слоя в таблице переходов со сложностью O (1) Обратите внимание, что высота слоя узла заголовка не учитывается.

API таблицы перехода

Список всех API-интерфейсов операций для таблиц переходов.

функция	эффект	временная сложность
zslCreate	Создайте новую таблицу переходов.	O(1)
zslFree	Освободить данную таблицу переходов и все узлы, содержащиеся в таблице.	НА) ,Nдлина таблицы пропуска.
zslInsert	Добавляет новый узел с заданным элементом и оценкой в ​​таблицу пропуска.	Среднее O(\log N), наихудшее O(N),Nдлина таблицы пропуска.
zslDelete	Удаляет узел в таблице пропуска, который содержит данный элемент и оценку.	Среднее O(\log N), наихудшее O(N),Nдлина таблицы пропусков.
zslGetRank	Возвращает ранг в таблице пропуска узла, содержащего данный элемент и оценку.	Среднее O(\log N), наихудшее O(N),Nдлина таблицы пропусков.
zslGetElementByRank	Возврат таблицы переходов к узлу с заданным рейтингом.	Среднее O(\log N), наихудшее O(N),Nдлина таблицы пропусков.
zslIsInRange	Учитывая диапазон баллов, например.0прибыть15,20прибыть28и т. д., если заданный диапазон баллов входит в диапазон баллов таблицы пропуска, затем вернуть1, иначе возврат0.	Эту проверку можно выполнить со сложностью O(1), пропустив узлы заголовка и нижнего колонтитула таблицы.
zslFirstInRange	Учитывая диапазон оценок, вернуть первый узел в списке пропуска, который соответствует этому диапазону.	O(\log N) в среднем, O(N) в худшем случае.Nдлина таблицы пропусков.
zslLastInRange	Учитывая диапазон оценок, вернуть последний узел в списке пропуска, который соответствует этому диапазону.	O(\log N) в среднем, O(N) в худшем случае.Nдлина таблицы пропусков.
zslDeleteRangeByScore	Учитывая диапазон оценок, удалите все узлы в списке пропуска в этом диапазоне.	НА) ,Nколичество удаленных узлов.
zslDeleteRangeByRank	Учитывая диапазон рангов, удалите все узлы в списке переходов в пределах этого диапазона.	НА) ,Nколичество удаленных узлов.

Интервью: зачем использовать Redis Jump Table (Skiplist) вместо того, чтобы использовать красно-черный?

1. Сложность skiplist такая же, как у красно-черного дерева, и его проще реализовать.
2. В параллельной среде у Skiplist есть еще одно преимущество. Красно-черные деревья могут нуждаться в выполнении некоторых операций перебалансировки при вставке и удалении. Такие операции могут включать другие части всего дерева, а операции Skiplist, очевидно, более локальны. Блокировки должны быть привязаны к меньшему количеству узлов, поэтому в таких случаях производительность выше.

Подробности см. в статье Херба Саттера.Choose Concurrency-Friendly Data Structures.

Кроме того, в этой статье на стр. 50–53 приведены более подробные описания и сравнения:Ничего себе. Кроме .CAM.AC.UK/research/ хотя…

Приложение: Почему разработчик выбрал Skiplist?The Skip list

There are a few reasons:

1. They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.

About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.

Суммировать

• Таблица переходов — это упорядоченная коллекция одной из базовых реализаций, кроме которой в Redis нет других приложений.
• Реализация таблицы пропуска Redis предоставляетсяzskiplistиzskiplistNodeсостоит из двух структур, гдеzskiplistИспользуется для сохранения информации таблицы переходов (например, узла заголовка, узла нижнего колонтитула, длины) иzskiplistNodeиспользуется для представления узла таблицы пропуска.
• Высота слоя каждого узла таблицы пропуска равна1к32случайные числа между ними.
• В одной и той же таблице пропуска несколько узлов могут содержать одну и ту же оценку, но объект-член каждого узла должен быть уникальным.
• Узлы в таблице переходов сортируются в соответствии с размером оценки, а когда оценки совпадают, узлы сортируются в соответствии с размером объекта-члена.

использованная литература

• стол для прыжков

Статья постоянно обновляется, можно поискать на официальном аккаунте »дайм тек"Прочитайте впервые эту статью GitHuborg_hejianhui/JavaStudyОн был записан, добро пожаловать в Star.