Все мы знаем, что у односвязного списка есть фатальная слабость. Поиск любого узла имеет по крайней мере O(n) временную сложность. Он должен пройти через весь связанный список. Есть ли способ повысить эффективность поиска в связанном списке?
Структура данных SkipList использует стратегию «пространство во времени» для повышения эффективности поиска за счет создания многоуровневого индекса для связанного списка.Давайте сначала представим базовую теорию списка пропуска, а затем рассмотрим реализацию в Redis.
1. Список пропуска (SkipList)
Это двусторонний связанный список с часовым. Связанный список в большинстве случаев имеет такую структуру. То же самое. Но недостатком является то, что если вы хотите запросить узел, вам потребуется O(n).
Что, если мы добавим индекс в связанный список? Конечно, предполагается, что нижний связанный список упорядочен, иначе индекс не имеет смысла.
Пусть указатель головы HEAD указывает на самый высокий индекс, я вытащил слой индекса, так что даже если вы посмотрите на узел 2222 три сравнения.
В первый раз: по сравнению с узлом 2019 года обнаружено, что он больше, чем 2019 год, а затем продолжить
Второй раз: по сравнению с 2100 узлами обнаруживается, что это все же больше, и продолжить позже
Третий раз: индекс этого слоя достиг конца, указать на следующий узел с более низким индексом, продолжить сравнение и найти узел
Однако по мере увеличения количества узлов связанного списка и повышения уровня индекса разрыв в эффективности будет очевиден. Рисунок нарисован не мной, он взят с рисунка г-на Ван Чжэна из Geek Time.
Видите ли, изначально требовалось 62 операции сравнения, но благодаря пятиуровневому индексу требуется только 4 сравнения, и эффективность таблицы переходов можно увидеть с первого взгляда.
Чтобы узнать разницу между конкретным списком переходов и связанным списком, мы проанализируем и сравним временную сложность соответствующих операций.
1. Вставить операцию узла
Исходная операция вставки двустороннего связанного списка (далее — связанный список) имеет временную сложность O(1), но здесь речь идет об упорядоченном связанном списке, поэтому вставка узла должна как минимум найти место, куда он должен быть вставлен перед выполнением операции вставки, поэтому эффективность вставки связанного списка составляет O (n).
Таблица переходов (далее именуемая таблицей переходов) по-прежнему требует двух шагов для завершения операции вставки, сначала нахождения позиции вставки, а затем выполнения операции вставки. Мы создали связанный список с N узлами, который имеет индексы уровня K и предполагает, что индекс разбит на один уровень через каждые два интервала узлов.
Два узла на уровне k, 4 узла на уровне k-1, 8 узлов на уровне k-2... n узлов на уровне 1,
1：n
2：1/2 * n
3：1/2^2 * n
.....
.....
k：1/2^(k-1) * n
1/2^(k-1) * n представляет количество узлов в k-м слое, можно получить 1/2^(k-1) * n=2, k равно logn, то есть , N узлам потребуется создать таблицу пропуска. Индекс слоя журнала, включая собственный слой связанного списка.
Когда мы хотим найти определенный узел, нам нужно начать с индекса самого высокого уровня.Согласно нашему методу построения, определенный узел должен располагаться между двумя узлами индекса, поэтому каждый слой может посетить не более трех узлов. Возможно, вам нужно это понимать, потому что поиск каждого уровня индекса основан на предыдущем уровне индекса.От предыдущего уровня индекса он либо больше (меньше) текущего узла индекса, но не больше ( меньше чем) его Узел в следующих двух позициях является следующим узлом индекса после текущего узла индекса, поэтому он может получить доступ к трем узлам.
Исходя из этого вывода, временная сложность вставки элемента в список пропуска составляет: O(logn). Эта временная сложность равна временной сложности бинарного поиска, поэтому иногда мы также называем таблицу переходов связанным списком, реализующим бинарный поиск.
Очевидно, что операция вставки пропускаемого списка превосходит связанный список.
2. Изменить и удалить запрос
Эти три операции узла на самом деле несопоставимы.Операции изменения и удаления связанных списков эквивалентны спискам пропуска. Что касается запроса, то, как мы сказали выше, связанный список не меньше O(n), а список переходов — O(logn).
Кроме того, все мы знаем, что красно-черное дерево будет вращаться, чтобы сбалансировать дерево после каждой вставки узла, поэтому на самом деле существует такая проблема со списком пропуска, то есть непрерывная вставка приведет к тому, что нижележащие узлы связанного списка будут индексные слои все еще так много. В крайних случаях все узлы добавляются справа от индексного узла последнего уровня, что, в свою очередь, вырождает список пропуска в связанный список.
Короче говоря, после вставки большого количества узлов, если индекс не обновляется, таблица пропуска не сможет гарантировать эффективность, как всегда. Решение также очень простое, то есть каждый раз, когда вставляется узел, запускается обновление узла индекса.Давайте подробно рассмотрим стратегию обновления.
Как правило, в таблице пропуска используется случайная функция.Эта случайная функция будет генерировать случайное число в соответствии с текущей структурой таблицы пропуска после добавления нового узла в таблицу пропуска.Конечно, это значение должно быть меньше, чем максимальное значение индексного слоя, предполагая, что это значение равно m , тогда таблица пропуска будет генерировать индекс от 1 до m слоев. Таким образом, выбор или реализация этой случайной функции очень важны.Мы не будем обсуждать это здесь.Вы можете увидеть, как эта случайная функция реализована в реализации различных списков пропуска, как правило, это внутренняя реализация ConcurrentSkipListMap в Java.Структура SkipList , и, конечно же, реализация в Redis, которую мы собираемся представить.
Вышеизложенное является основным теоретическим содержанием структуры данных таблицы переходов.Далее давайте посмотрим на реализацию в Redis.
2. Таблица переходов в Redis
Как упоминалось выше, Redis реализует таблицу пропуска сам по себе, но цель состоит в том, чтобы предоставить услуги для своих высокоуровневых абстрактных структур данных, таких как упорядоченные коллекции, поэтому, когда мы анализируем исходный код, неизбежно будут задействованы некоторые, казалось бы, бесполезные структуры. логика кода, но это тоже очень важно. Мы также упомянем содержание, связанное с упорядоченными наборами, но не будем разбивать их подробно. Основное внимание уделяется реализации списка пропуска.
Структура данных таблицы пропуска определяется следующим образом:
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
Каждый узел в списке пропуска представлен структурой данных zskiplistNode, а начало и конец соответственно указывают на начало и конец списка самого нижнего связанного списка. length указывает, сколько узлов находится в самом нижнем связанном списке текущего списка пропуска, а level записывает самый высокий уровень индекса текущего списка пропуска.
Структура zskiplistNode следующая:
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
Исходный код Redis, который я извлек здесь, относится к версии 4.0.В предыдущей версии атрибут ele был типом RedisObject, но теперь это строковый тип, что означает, что таблица пропуска используется только для хранения строковых данных.
score записывает счет текущего узла. Связный список нижнего уровня соединен последовательно в соответствии с размером счета, и когда мы запрашиваем узел, мы обычно также передаем значение счета узла. В конце концов, числовой Типы удобнее.
Обратный указатель указывает на предыдущий узел, почему он обратный, об этом мы поговорим позже.
Ключевым моментом является уровень. Существует массив уровней, и каждый элемент представляет собой структуру типа zskiplistLevel. Тип zskiplistLevel включает в себя прямой указатель и значение диапазона. Что это значит? Давайте немного скажем.
Теоретически нижний слой списка пропуска представляет собой двусторонний связанный список, а затем на его основе устанавливаются многоуровневые индексные узлы, однако в реальной реализации кода эту структуру описать непросто, поэтому необходимо сломайте существующее инерционное мышление, и тогда вы сможете понять реализацию в Redis. Фактически, как и структура zskiplistNode, которую мы представили выше,Помимо хранения данных самого узла, каждый узел также сохраняет ссылку на узел узла в каждом индексном слое всей таблицы переходов через массив уровней, конкретная структура выглядит следующим образом:
Вся таблица прыжков в основном имеет следующую структуру:
Обратный указатель каждого узла указывает на узел перед ним, а массив уровней в каждом узле записывает, в каких индексных слоях таблицы переходов находится текущий узел, и последовательно соединяет узлы этого индекса слоя через его прямой указатель. , 0 — первый слой, 1 — второй слой и так далее. span представляет промежуток между текущим узлом и следующим узлом, мы поговорим об этом в коде позже, не имеет значения, если вы пока не понимаете этого.
По сути, таблица пропуска является такой структурой.Приведенное выше изображение по-прежнему очень важно, включая реализацию исходного кода, которую мы представим позже, что также очень полезно для вашего понимания. (Ведь я рисовала давно..)
Вот дополнительное предложение. Существует также структура упорядоченного набора, определенная вместе со связанной структурой таблицы пропуска. Многие люди скажут, что упорядоченный набор в Redis реализуется таблицей пропуска. Это предложение хорошее, но оно предвзято .
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
Чтобы быть точным, упорядоченный набор в Redis реализуется словарем, который мы представили ранее, плюс таблица пропуска Отношение сопоставления между данными, сохраненными в словаре, и оценкой: каждый раз, когда данные вставляются, они будут запрашиваться из словаря. , если он уже существует, он больше не будет вставлен, а повторяющиеся данные не допускаются в упорядоченном наборе.
Давайте посмотрим на реализацию соответствующего кода таблицы пропуска в Redis.
1. Инициализация таблицы переходов
Код для инициализации таблицы переходов в Redis выглядит следующим образом:
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
return zn;
}
/* Create a new skiplist. */
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
//分配内存空间
zsl = zmalloc(sizeof(*zsl));
//默认只有一层索引
zsl->level = 1;
//0 个节点
zsl->length = 0;
//1、创建一个 node 节点，这是个哨兵节点
//2、为 level 数组分配 ZSKIPLIST_MAXLEVEL=32 内存大小
//3、也即 redis 中支持索引最大 32 层
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
//为哨兵节点的 level 初始化
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
}
zslCreate используется для инициализации таблицы переходов, что относительно просто.Я также дал основные комментарии, которые не буду повторяться здесь.Подчеркнуто, что таблица переходов, реализованная в redis, допускает до 32 слоев индексов.Это тоже производительность и С точки зрения памяти, слишком много индексных слоев неизбежно будут занимать больше места в памяти, и 32 является более подходящим значением.
2. Вставьте узел
Кода для вставки узла много, и это немного сложно, надеюсь, у вас хватит терпения проанализировать его вместе со мной.
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
//update数组将用于记录新节点在每一层索引的目标插入位置
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
//rank数组记录目标节点每一层的排名
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
serverAssert(!isnan(score));
//指向哨兵节点
x = zsl->header;
//这一段就是遍历每一层索引，找到最后一个小于当前给定score值的节点
//从高层索引向底层索引遍历
for (i = zsl->level-1; i >= 0; i--) {
//rank记录的是节点的排名，正常情况下给它初始值等于上一层目标节点的排名
//如果当前正在遍历最高层索引，那么这个初始值暂时给0
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
//我们说过level结构中，span表示的是与后面一个节点的跨度
//rank[i]最终会得到我们要找的目标节点的排名，也就是它前面有多少个节点
rank[i] += x->level[i].span;
//挪动指针
x = x->level[i].forward;
}
update[i] = x;
}
//至此，update数组中已经记录好，每一层最后一个小于给定score值的节点
//我们的新节点只需要插在他们后即可
//random算法获取一个平衡跳表的level值，标志着我们的新节点将要在哪些索引出现
//具体算法这里不做分析，你也可以私下找我讨论
level = zslRandomLevel();
//如果产生值大于当前跳表最高索引
if (level > zsl->level) {
//为高出来的索引层赋初始值，update[i]指向哨兵节点
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
//根据score和ele创建节点
x = zslCreateNode(level,score,ele);
//每一索引层得进行新节点插入，建议对照我之前给出的跳表示意图
for (i = 0; i < level; i++) {
//断开指针，插入新节点
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
//rank[0]等于新节点再最底层链表的排名，就是它前面有多少个节点
//update[i]->level[i].span记录的是目标节点与后一个索引节点之间的跨度，即跨越了多少个节点
//得到新插入节点与后一个索引节点之间的跨度
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
//修改目标节点的span值
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
//如果上面产生的平衡level大于跳表最高使用索引，我们上面说会为高出部分做初始化
//这里是自增他们的span值，因为新插入了一个节点，跨度自然要增加
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
//修改 backward 指针与 tail 指针
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
Всю методику я уже прокомментировал, не буду подробно останавливаться на деталях, можете со мной общаться и обсуждать, общая логика разбита на три шага.
- Перейдите от самого высокого уровня индекса, найдите его предшествующий узел в соответствии с оценкой и сохраните его с массивом обновлений.
- Каждый слой должен вставлять узлы и вычислять значение диапазона обновления.
- Изменить обратный указатель и хвостовой указатель
Удаление узла аналогично: сначала нужно найти целевой узел в соответствии со значением очков, а затем разорвать соединение между передним и задним узлами, чтобы завершить удаление узла.
3. Специальные операции запроса
Поскольку поле span добавлено в реализацию таблицы пропуска Redis, оно записывает диапазон между текущим узлом и следующим узлом, поэтому он имеет следующие методы запроса.
а. zslGetRank
Возвращает ранг в таблице пропуска узла, содержащего данный элемент и оценку.
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x;
unsigned long rank = 0;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) <= 0))) {
rank += x->level[i].span;
x = x->level[i].forward;
}
/* x might be equal to zsl->header, so test if obj is non-NULL */
if (x->ele && sdscmp(x->ele,ele) == 0) {
return rank;
}
}
return 0;
}
Вы обнаружите, что основной код этого метода на самом деле является частью нашего метода вставки узлов, а значение ранжирования целевого узла получается путем накопления интервалов.
б. zslGetElementByRank
Элемент запроса по заданному рангу. Этот способ проще.
в. зслисинранже
Учитывая диапазон оценок, например от 0 до 10, вернуть 1, если заданный диапазон оценок включен в диапазон оценок таблицы пропуска, и 0 в противном случае.
г. зслфирстинранже
Учитывая диапазон оценок, вернуть первый узел в списке пропуска, который соответствует этому диапазону.
е. зслделетеранжебискоре
Учитывая диапазон оценок, удалите все узлы в списке пропуска в этом диапазоне.
е. zslDeleteRangeByRank
Учитывая диапазон рангов, удалите все узлы в списке переходов в пределах этого диапазона.
На самом деле, все перечисленные ниже методы удаления узлов на основе ранжирования или даже запроса диапазона основаны на поле span, что является одной из причин, по которой метод вставки должен вычислять поле span с помощью такой сложной логики вычислений.
Подводя итог, список с пропуском предназначен для упорядоченных коллекций.Многоуровневый индекс повышает эффективность поиска связанного списка до уровня O(logn), но модификация и удаление по-прежнему O(1), что является отличными данными. структура и redis Реализация в реализации реализует каждый узел в структуру, похожую на здание, то есть наш индексный слой, что очень гениально.
Мы кратко представим таблицу пропуска здесь Если у вас есть какие-либо вопросы, вы можете обсудить их со мной.
Обратите внимание на публику и не теряйтесь, программист, который любит делиться. Официальный аккаунт отвечает на "1024" и добавляет авторский WeChat для обсуждения и изучения вместе! Все материалы кода кейса, использованные в каждой статье, будут загружены на мой личный github. GitHub.com/один батат/о… Добро пожаловать!