企业官网建设流程全解析

按每两个节点生成一个索引，则有第一层索引节点的个数为n/2

1. 时间复杂度O(logn) 最坏O（n）

2. 空间复杂度O(n)

一. 跳表的定义
跳表，又叫做跳跃表、跳跃列表，在有序链表的基础上增加了“跳跃”的功能
跳表在原来的有序链表上加上了多级索引，通过索引来快速查找；可以支持快速的删除、插入和查找操作。
跳表实际上是一种增加了前向指针的链表，是一种随机化的数据结构
Redis中 的 SortedSet、LevelDB 中的 MemTable 都用到了跳表
对比平衡树, 跳表的实现和维护会更加简单, 跳表的搜索、删除、添加的平均时间复杂度是 O(logn)

跳表（Skip List）-CSDN博客

跳表和红黑树对比

查找: 红黑树查找操作的时间复杂度在最坏情况下为O(logn)红黑树在查找单个节点时效率很高，但如果需要按照区间查找数据,比不上跳表

• 如果你的应用场景主要是单点查询，并且对数据结构的内存使用有较高要求，那么红黑树可能是一个更好的选择。

红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，Skip需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。

#include <iostream> #include <cstdlib> #include <cmath> #include <cstring> #include <mutex> #include <fstream> #define STORE_FILE "store/dumpFile" std::string delimiter = ":"; //Class template to implement node template<typename K, typename V> class Node { public: Node() {} Node(K k, V v, int); ~Node(); K get_key() const; V get_value() const; void set_value(V); // Linear array to hold pointers to next node of different level Node<K, V> **forward; int node_level; private: K key; V value; }; template<typename K, typename V> Node<K, V>::Node(const K k, const V v, int level) { this->key = k; this->value = v; this->node_level = level; // level + 1, because array index is from 0 - level this->forward = new Node<K, V> *[level + 1]; // Fill forward array with 0(NULL) memset(this->forward, 0, sizeof(Node<K, V> *) * (level + 1)); }; template<typename K, typename V> Node<K, V>::~Node() { delete[]forward; }; template<typename K, typename V> K Node<K, V>::get_key() const { return key; }; template<typename K, typename V> V Node<K, V>::get_value() const { return value; }; template<typename K, typename V> void Node<K, V>::set_value(V value) { this->value = value; }; // Class template for Skip list template<typename K, typename V> class SkipList { public: SkipList(int); ~SkipList(); int get_random_level(); Node<K, V> *create_node(K, V, int); int insert_element(K, V); void display_list(); bool search_element(K); void delete_element(K); void dump_file(); void load_file(); //递归删除节点 void clear(Node<K, V> *); int size(); private: void get_key_value_from_string(const std::string &str, std::string *key, std::string *value); bool is_valid_string(const std::string &str); private: // Maximum level of the skip list int _max_level; // current level of skip list int _skip_list_level; // pointer to header node Node<K, V> *_header; // file operator std::ofstream _file_writer; std::ifstream _file_reader; // skiplist current element count int _element_count; }; // create new node template<typename K, typename V> Node<K, V> *SkipList<K, V>::create_node(const K k, const V v, int level) { Node<K, V> *n = new Node<K, V>(k, v, level); return n; } // Insert given key and value in skip list // return 1 means element exists // return 0 means insert successfully /* +------------+ | insert 50 | +------------+ level 4 +-->1+ 100 | | insert +----+ level 3 1+-------->10+---------------> | 50 | 70 100 | | | | level 2 1 10 30 | 50 | 70 100 | | | | level 1 1 4 10 30 | 50 | 70 100 | | | | level 0 1 4 9 10 30 40 | 50 | 60 70 100 +----+ */ template<typename K, typename V> int SkipList<K, V>::insert_element(const K key, const V value) { Node<K, V> *current = this->_header; // create update array and initialize it // update is array which put node that the node->forward[i] should be operated later // 用于记录从最高层到当前层（通常是新节点的随机层数）遍历过程中，每一层上最后一个不小于（或大于，取决于具体实现）待插入键值的节点的“前驱”节点 Node<K, V> *update[_max_level + 1]; // 用于存储待操作的节点，这些节点的 forward[i] 应该稍后被更新 memset(update, 0, sizeof(Node<K, V> *) * (_max_level + 1)); // start form highest level of skip list //// 从跳表的最高层开始向下查找 for (int i = _skip_list_level; i >= 0; i--) //因为 insert node 那里所有随机到的层级都插入了所以这里i-- 获得current = current->forward[i]; 这里就是向下走. 当没有i-- 的时候获得current = current->forward[i]; 就是向前走 { while (current->forward[i] != NULL && current->forward[i]->get_key() < key) { current = current->forward[i]; } update[i] = current; } // 移动到 level 0 的下一个节点 reached level 0 and forward pointer to right node, which is desired to insert key. current = current->forward[0]; // 如果当前节点不为空且其 key 等于要查找的 key，则表示节点已存在 if current node have key equal to searched key, we get it if (current != NULL && current->get_key() == key) { std::cout << "key: " << key << ", exists" << std::endl; return 1; } // if current is NULL that means we have reached to end of the level // if current's key is not equal to key that means we have to insert node between update[0] and current node if (current == NULL || current->get_key() != key) { // Generate a random level for node int random_level = get_random_level(); // 随机要更新多少个层 // If random level is greater thar skip list's current level, initialize update value with pointer to header if (random_level > _skip_list_level) { for (int i = _skip_list_level + 1; i < random_level + 1; i++) { update[i] = _header; } _skip_list_level = random_level; } // create new node with random level generated Node<K, V> *inserted_node = create_node(key, value, random_level); // // update[i]->forward[i]; // i层的下一个节点 // insert node for (int i = 0; i <= random_level; i++) { //update[i] 是前驱节点. update[i]->forward[i] 就是i层前驱节点的下一层 // update[i]->forward[i] i层不小于的下一个节点 inserted_node->forward[i] = update[i]->forward[i]; // 更新新节点的 forward 指针 ; 更新节点的下一个指针. update[i]->forward[i] = inserted_node; // 更新前驱节点的 forward 指针 } std::cout << "Successfully inserted key:" << key << ", value:" << value << std::endl; _element_count++; } return 0; } // Display skip list template<typename K, typename V> void SkipList<K, V>::display_list() { std::cout << "\n*****Skip List*****" << "\n"; for (int i = 0; i <= _skip_list_level; i++) { Node<K, V> *node = this->_header->forward[i]; std::cout << "Level " << i << ": "; while (node != NULL) { std::cout << node->get_key() << ":" << node->get_value() << ";"; node = node->forward[i]; } std::cout << std::endl; } } // Dump data in memory to file template<typename K, typename V> void SkipList<K, V>::dump_file() { std::cout << "dump_file-----------------" << std::endl; _file_writer.open(STORE_FILE); Node<K, V> *node = this->_header->forward[0]; while (node != NULL) { _file_writer << node->get_key() << ":" << node->get_value() << "\n"; std::cout << node->get_key() << ":" << node->get_value() << ";\n"; node = node->forward[0]; } _file_writer.flush(); _file_writer.close(); return; } // Load data from disk template<typename K, typename V> void SkipList<K, V>::load_file() { _file_reader.open(STORE_FILE); std::cout << "load_file-----------------" << std::endl; std::string line; std::string *key = new std::string(); std::string *value = new std::string(); while (getline(_file_reader, line)) { get_key_value_from_string(line, key, value); if (key->empty() || value->empty()) { continue; } // Define key as int type insert_element(stoi(*key), *value); std::cout << "key:" << *key << "value:" << *value << std::endl; } delete key; delete value; _file_reader.close(); } // Get current SkipList size template<typename K, typename V> int SkipList<K, V>::size() { return _element_count; } template<typename K, typename V> void SkipList<K, V>::get_key_value_from_string(const std::string &str, std::string *key, std::string *value) { if (!is_valid_string(str)) { return; } *key = str.substr(0, str.find(delimiter)); *value = str.substr(str.find(delimiter) + 1, str.length()); } template<typename K, typename V> bool SkipList<K, V>::is_valid_string(const std::string &str) { if (str.empty()) { return false; } if (str.find(delimiter) == std::string::npos) { return false; } return true; } // Delete element from skip list template<typename K, typename V> void SkipList<K, V>::delete_element(K key) { Node<K, V> *current = this->_header; Node<K, V> *update[_max_level + 1]; memset(update, 0, sizeof(Node<K, V> *) * (_max_level + 1)); // start from highest level of skip list for (int i = _skip_list_level; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->get_key() < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current != NULL && current->get_key() == key) { // start for lowest level and delete the current node of each level for (int i = 0; i <= _skip_list_level; i++) { //如果在层级i上，update[i]的前向指针并不指向current，则中断循环 // 这意味着在当前层级上面,没有了. 就是这个节点只有0 - i才赋值了索引. // if at level i, next node is not target node, break the loop. if (update[i]->forward[i] != current) break; // 更新update[i]在层级i上的前向指针，使其指向current的下一个节点 // 这样就从当前层级上移除了current节点的引用 update[i]->forward[i] = current->forward[i]; } // Remove levels which have no elements while (_skip_list_level > 0 && _header->forward[_skip_list_level] == 0) { _skip_list_level--; } std::cout << "Successfully deleted key " << key << std::endl; delete current; _element_count--; } return; } // Search for element in skip list /* +------------+ | select 60 | +------------+ level 4 +-->1+ 100 | | level 3 1+-------->10+------------------>50+ 70 100 | | level 2 1 10 30 50| 70 100 | | level 1 1 4 10 30 50| 70 100 | | level 0 1 4 9 10 30 40 50+-->60 70 100 */ template<typename K, typename V> bool SkipList<K, V>::search_element(K key) { Node<K, V> *current = _header; // start from highest level of skip list for (int i = _skip_list_level; i >= 0; i--) { while (current->forward[i] && current->forward[i]->get_key() < key) { current = current->forward[i]; printf("比较1次\n"); } } //reached level 0 and advance pointer to right node, which we search current = current->forward[0]; // if current node have key equal to searched key, we get it if (current and current->get_key() == key) { std::cout << "Found key: " << key << ", value: " << current->get_value() << std::endl; return true; } std::cout << "Not Found Key:" << key << std::endl; return false; } // construct skip list template<typename K, typename V> SkipList<K, V>::SkipList(int max_level) { this->_max_level = max_level; this->_skip_list_level = 0; this->_element_count = 0; // create header node and initialize key and value to null K k; V v; this->_header = new Node<K, V>(k, v, _max_level); }; template<typename K, typename V> SkipList<K, V>::~SkipList() { if (_file_writer.is_open()) { _file_writer.close(); } if (_file_reader.is_open()) { _file_reader.close(); } //递归删除跳表链条 if (_header->forward[0] != nullptr) { clear(_header->forward[0]); } delete (_header); } template<typename K, typename V> void SkipList<K, V>::clear(Node<K, V> *cur) { if (cur->forward[0] != nullptr) { clear(cur->forward[0]); } delete (cur); } template<typename K, typename V> int SkipList<K, V>::get_random_level() { int k = 1; while (rand() % 2) { k++; } k = (k < _max_level) ? k : _max_level; return k; }; // vim: et tw=100 ts=4 sw=4 cc=120

#include "skiplist.h" #define FILE_PATH "./store/dumpFile" int main(int argc, char ** argv) { // LogServerController::createIns()->startGame(argc, argv); // 键值中的key用int型，如果用其他类型，需要自定义比较函数 // 而且如果修改key的类型，同时需要修改skipList.load_file函数 SkipList<int, std::string> skipList(6); skipList.insert_element(1, "学"); // skipList.display_list(); skipList.insert_element(3, "算法"); // skipList.display_list(); skipList.insert_element(2, "认准"); skipList.display_list(); skipList.insert_element(8, "微信公众号：代码随想录"); skipList.insert_element(9, "学习"); skipList.insert_element(19, "算法不迷路"); skipList.insert_element(19, "赶快关注吧你会发现详见很晚！"); std::cout << "skipList size:" << skipList.size() << std::endl; skipList.dump_file(); // skipList.load_file(); skipList.display_list(); skipList.search_element(9); skipList.search_element(18); skipList.display_list(); skipList.delete_element(3); skipList.delete_element(7); std::cout << "skipList size:" << skipList.size() << std::endl; skipList.display_list(); }

5000数据量的时候和红黑树性能对比

前面是跳表后面是红黑树

#include "skiplist.h" #define FILE_PATH "./store/dumpFile" int main(int argc, char ** argv) { // LogServerController::createIns()->startGame(argc, argv); // 键值中的key用int型，如果用其他类型，需要自定义比较函数 // 而且如果修改key的类型，同时需要修改skipList.load_file函数 SkipList<int, std::string> skipList(6); map<int, string> testMap; auto cur = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; if (i % 3 == 0) { skipList.delete_element(a); } else { skipList.insert_element(a, ""); } } auto cur2 = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; testMap.emplace(make_pair(a, "")); if (i % 3 == 0) { testMap.erase(a); } else { testMap.emplace(make_pair(a, "")); } } auto cur3 = TimeUtil::gettimeU(); printf("跳: %ld_插__ 红:%ld\n", cur2 - cur, cur3 - cur2); cur = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; skipList.search_element(a); } cur2 = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; testMap.find(a); } cur3 = TimeUtil::gettimeU(); printf("跳: %ld_找__ 红:%ld\n", cur2 - cur, cur3 - cur2); cur = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; skipList.delete_element(a); } cur2 = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; testMap.erase(a); } cur3 = TimeUtil::gettimeU(); printf("跳: %ld__删_ 红:%ld\n", cur2 - cur, cur3 - cur2); cur = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; skipList.search_element(a); } cur2 = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; testMap.find(a); } cur3 = TimeUtil::gettimeU(); printf("跳: %ld_找__ 红:%ld\n", cur2 - cur, cur3 - cur2); cur = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; skipList.insert_element(a, ""); } cur2 = TimeUtil::gettimeU(); for (int i = 0; i < 50000; i++) { int a = rand() % 5000; testMap.emplace(make_pair(a, "")); } cur3 = TimeUtil::gettimeU(); printf("跳: %ld_插__ 红:%ld\n", cur2 - cur, cur3 - cur2); cur = TimeUtil::gettimeU(); }

开了O2

没开O2

50000数据量的时候内存对比,第一个是跳.

vector 自己实现的二分查找效率和map 和lower_bound 差别不大. 但是都略微优与他们 ,毕竟都是对数级

int find (vector<int>& arr, int target) { int left = 0, right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (arr[mid] == target) { return true; // 找到目标值 } else if (arr[mid] < target) { left = mid + 1; // 调整左边界 } else { right = mid - 1; // 调整右边界 } } return false; // 未找到目标值 }

==========================leveldb======================================

template <typename Key, class Comparator> int SkipList<Key, Comparator>::RandomHeight() { // Increase height with probability 1 in kBranching static const unsigned int kBranching = 4; int height = 1; while (height < kMaxHeight && rnd_.OneIn(kBranching)) { height++; } assert(height > 0); assert(height <= kMaxHeight); return height; }

为什么 用4 ,,

• 所有节点都在第 0 层；
• 约1/4的节点能到第 1 层；
• 约1/16的节点能到第 2 层；
• 约1/64的节点能到第 3 层。

如果设为 2, 如果1600w数据的时候12层的话, 顶层会太密了,,每个节点平均需要更多后继指针，占用更多内存。设成 4 则高层更稀疏，节省内存，但查找时可能需要多走几步。

===============================================================

GitHub - youngyangyang04/Skiplist-CPP: A tiny KV storage based on skiplist written in C++ language| 使用C++开发，基于跳表实现的轻量级键值数据库🔥🔥 🚀

GitHub1s