Redis核心数据结构——跳表（生成数据到文件和从文件中读取数据、模块合并、）

生成文件和从文件中读取数据。

需求如下：

你的任务是实现 SkipList 类中的数据持久化成员函数和数据加载成员函数。 

持久化数据成员函数签名：void dump_file();

该成员函数负责将存储引擎内的数据持久化到文件中。数据的持久化格式是将每个键值对写入文件的单独一行，采用key:value的格式。这种方式不仅确保了数据格式的一致性，还便于数据的恢复和解析。 

读取数据成员函数签名：void load_file(); 

此成员函数的目的是从文件中读取之前持久化的数据，并将其加载到存储引擎中。读取的数据格式遵循每行一个key:value键值对的规则。在数据加载过程中，成员函数还需确保跳表的索引能够被正确地重建，以保持数据的快速访问和检索性能。

其实看起来蛮简单的，就是把原本数据按照一定格式读入到文件中，和从文件中读取数据再调用insert_element函数就行了。但实现起来还是遇到了几个坑的。

首先是文件读写，这个网上版本很多，随意选择一种就行。

包含如下头文件：

#include <fstream>
#include <iostream>

在要编写的dump_file函数里写明绝对路径，然后修改下print拿过来用就行了。代码如下：

    void dump_file() {std::ofstream out("D:\\dev_c++\\destination\\out.txt");if (out.is_open()) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {out << cur->getKey() << ":" << cur->get_value() << '\n';cur = cur->forwards[curlevel];}curlevel--;}out.close();}}

这个在在线判题系统里似乎修改不了，需要用本地C++编译器。然后还会在time(0)出报错，需要加上如下头文件：

#include <sys/time.h>

实现效果如图，还用的删除跳表那里的输入输出数据

再来看读入数据：

这个首先要判断是否打开了文件，没打开直接报错，在线判题网上里就是直接报错的。所以我们还是要用编译器。之后就是对输入字符串进行处理，循环遍历找到':'下标作为分隔符下标，以此为依据调用substr函数即可。

代码如下：

    void load_file() {std::ifstream in("D:\\dev_c++\\destination\\out.txt");char buffer[256];if (!in.is_open()) {std::cout << "open error";} else {while (!in.eof()) {std::string s;in >> s;int index = 0;if (s.size() == 0) return; for (int i = 0; i < s.length(); i++) {if (s[i] == ':') {index = i;break;}}
//              std::cout << s << ' ';std::string s1 = s.substr(0, index);std::string s2 = s.substr(index + 1, s.length() - 1 - index); //下标从index+1开始std::cout << s1 << s2 << std::endl;
//              int key = std::stoi(s1);int value = std::stoi(s2);insert_element(key, value);}}}

这个实现的就只是int类型的读取文件。

运行效果如图：

由于我们采用的是随机层数的机制，所以每次结果层数会不一致，也很正常。这也是跳表好玩的地方之一了。

整体代码如下：

#include<stdlib.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <sys/time.h>template<typename K, typename V>
class Node {
private:K key;V val;int node_level;public:Node** forwards;public:Node(K inkey, V value, int level): key(inkey), val(value), node_level(level),forwards(nullptr) {this->forwards = new Node<K, V>*[node_level+1];memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));}~Node(){delete forwards;};K getKey() const {return key;}V get_value() const {return val;}int getLevel() const {return node_level;}void set_value(V value) {val = value;}};template<typename K, typename V>
class SkipList {
private:Node<K,V>* HeadNode = nullptr;int _maxlevel = 0;int temp_level = 0;
public:SkipList(int maxlevel = 500) {_maxlevel = maxlevel;HeadNode = new Node<K, V>(K(),V(),maxlevel);}~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }int getRandomLevel() {srand((int)time(0));int k = 1;while (rand() % 2) {k++;}k = (k < _maxlevel) ? k : _maxlevel;return k;}int insert_element(const K key, const V value) {int flag = 0;Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode;while (cur) {if (cur->getKey() == key) {flag = 1;cur->set_value(value);}cur = cur->forwards[curlevel]; }curlevel--;}if (flag == 1) return 1;Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();curlevel = newNode->getLevel();while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() > newNode->getKey()) {prev->forwards[curlevel] = newNode;newNode->forwards[curlevel] = cur;break;} cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}   if (!cur)prev->forwards[curlevel] = newNode;curlevel--;}return 0;}bool search_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) return true;cur = cur->forwards[curlevel]; }curlevel--;}return false;}void delete_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) {prev->forwards[curlevel] = cur->forwards[curlevel];break;}cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}curlevel--;}}void print() {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];std::cout << "Level " << curlevel-1 << ": ";while (cur) {std::cout << cur->getKey() << ":" << cur->get_value() << ';';cur = cur->forwards[curlevel];}std::cout << std::endl;curlevel--;}}void dump_file() {std::ofstream out("D:\\dev_c++\\destination\\out.txt");if (out.is_open()) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {out << cur->getKey() << ":" << cur->get_value() << '\n';cur = cur->forwards[curlevel];}curlevel--;}out.close();}}void load_file() {std::ifstream in("D:\\dev_c++\\destination\\out.txt");char buffer[256];if (!in.is_open()) {std::cout << "open error";} else {while (!in.eof()) {std::string s;in >> s;int index = 0;if (s.size() == 0) return; for (int i = 0; i < s.length(); i++) {if (s[i] == ':') {index = i;break;}}
//                std::cout << s << ' ';std::string s1 = s.substr(0, index);std::string s2 = s.substr(index + 1, s.length() - 1 - index);
//                std::cout << s1 << s2 << std::endl;int key = std::stoi(s1);int value = std::stoi(s2);insert_element(key, value);}}}
};int main() {SkipList<int, int> mySkipList;// 插入删除数据 int n,k,m;std::cin >> n >> k >> m;while (n--) {int key, v, r;std::cin >> key >> v;r = mySkipList.insert_element(key,v);if (r == 0) std::cout << "Insert Success" << std::endl;else std::cout << "Insert Failed" << std::endl;}while (k--) {int key;std::cin >> key;mySkipList.delete_element(key);}while (m--) {int k;std::cin >> k;if (mySkipList.search_element(k)) std::cout << "Search Success" << std::endl;else std::cout << "Search Failed" << std::endl;}mySkipList.dump_file();// 读文件并展示 mySkipList.load_file();mySkipList.print();
}

模块合并

需求如下：

你的任务是创建一个 skiplist.h 的头文件，包含前面所有章节介绍的 Node 类和 SkipList 类，用以在其他程序中进行引用

其实主要也就是引入了锁，加上如下头文件：

#include <mutex> 

并且在插入删除数据函数前后分别加锁和解锁就行了，伪代码如下：

// 只有在插入和删除的时候，才会进行加锁
template <typename K, typename V>
int SkipList<K, V>::insert_element(const K key, const V value) {mtx.lock();  // 在函数第一句加锁// ... 算法过程（省略）if (current != NULL && current->get_key() == key) {std::cout << "key: " << key << ", exists" << std::endl;// 在算法流程中有一个验证 key 是否存在的过程// 在此处需要提前 return，所以提前解锁mtx.unlock();return 1;}// ... mtx.unlock();  // 函数执行完毕后解锁return 0;
}template <typename K, typename V>
void SkipList<K, V>::delete_element(K key) {mtx.lock();  // 加锁// ... 算法过程（省略）mtx.unlock();  // 解锁return;
}

最终代码如下：

#include<stdlib.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <mutex> 
#include <sys/time.h>std::mutex mtx; template<typename K, typename V>
class Node {
private:K key;V val;int node_level;public:Node** forwards;public:Node(K inkey, V value, int level): key(inkey), val(value), node_level(level),forwards(nullptr) {this->forwards = new Node<K, V>*[node_level+1];memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));}~Node(){delete forwards;};K getKey() const {return key;}V get_value() const {return val;}int getLevel() const {return node_level;}void set_value(V value) {val = value;}};template<typename K, typename V>
class SkipList {
private:Node<K,V>* HeadNode = nullptr;int _maxlevel = 0;int temp_level = 0;
public:SkipList(int maxlevel = 500) {_maxlevel = maxlevel;HeadNode = new Node<K, V>(K(),V(),maxlevel);}~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }int getRandomLevel() {srand((int)time(0));int k = 1;while (rand() % 2) {k++;}k = (k < _maxlevel) ? k : _maxlevel;return k;}int insert_element(const K key, const V value) {mtx.lock();int flag = 0;Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode;while (cur) {if (cur->getKey() == key) {flag = 1;cur->set_value(value);}cur = cur->forwards[curlevel]; }curlevel--;}if (flag == 1) return 1;Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();curlevel = newNode->getLevel();while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() > newNode->getKey()) {prev->forwards[curlevel] = newNode;newNode->forwards[curlevel] = cur;break;} cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}   if (!cur)prev->forwards[curlevel] = newNode;curlevel--;}mtx.unlock();return 0;}bool search_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) return true;cur = cur->forwards[curlevel]; }curlevel--;}return false;}void delete_element(K key) {mtx.lock();Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) {prev->forwards[curlevel] = cur->forwards[curlevel];break;}cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}curlevel--;}mtx.unlock();}void print() {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];std::cout << "Level " << curlevel-1 << ": ";while (cur) {std::cout << cur->getKey() << ":" << cur->get_value() << ';';cur = cur->forwards[curlevel];}std::cout << std::endl;curlevel--;}}void dump_file() {std::ofstream out("D:\\dev_c++\\destination\\out.txt");if (out.is_open()) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {out << cur->getKey() << ":" << cur->get_value() << '\n';cur = cur->forwards[curlevel];}curlevel--;}out.close();}}void load_file() {std::ifstream in("D:\\dev_c++\\destination\\out.txt");char buffer[256];if (!in.is_open()) {std::cout << "open error";} else {while (!in.eof()) {std::string s;in >> s;int index = 0;if (s.size() == 0) return; for (int i = 0; i < s.length(); i++) {if (s[i] == ':') {index = i;break;}}
//                std::cout << s << ' ';std::string s1 = s.substr(0, index);std::string s2 = s.substr(index + 1, s.length() - 1 - index);
//                std::cout << s1 << s2 << std::endl;int key = std::stoi(s1);int value = std::stoi(s2);insert_element(key, value);}}}
};int main() {SkipList<int, int> mySkipList;// 插入删除数据 int n,k,m;std::cin >> n >> k >> m;while (n--) {int key, v, r;std::cin >> key >> v;r = mySkipList.insert_element(key,v);if (r == 0) std::cout << "Insert Success" << std::endl;else std::cout << "Insert Failed" << std::endl;}while (k--) {int key;std::cin >> key;mySkipList.delete_element(key);}while (m--) {int k;std::cin >> k;if (mySkipList.search_element(k)) std::cout << "Search Success" << std::endl;else std::cout << "Search Failed" << std::endl;}mySkipList.dump_file();// 读文件并展示 mySkipList.load_file();mySkipList.print();
}

压力测试

测试结果如图

这一模块是要编写代码对所做项目进行测试，所用代码文件如下：

// 引入必要的头文件
#include <iostream> // 用于输入输出流
#include <chrono> // 用于高精度时间测量
#include <cstdlib> // 包含一些通用的工具函数，如随机数生成
#include <pthread.h> // 用于多线程编程
#include <time.h> // 用于时间处理函数
#include "./skiplist.h" // 引入自定义的跳表实现// 定义宏常量
#define NUM_THREADS 1 // 线程数量
#define TEST_COUNT 100000// 测试用的数据量大小
SkipList<int, std::string> skipList(18); // 创建一个最大层级为18的跳表实例// 插入元素的线程函数
void *insertElement(void* threadid) {long long tid; // 线程IDtid = (long long)threadid; // 将void*类型的线程ID转换为long型std::cout << tid << std::endl; // 输出线程IDint tmp = TEST_COUNT/NUM_THREADS; // 计算每个线程应该插入的元素数量// 循环插入元素for (int i=tid*tmp, count=0; count<tmp; i++) {count++;skipList.insert_element(rand() % TEST_COUNT, "a"); // 随机生成一个键，并插入带有"a"的元素}pthread_exit(NULL); // 退出线程
}// 检索元素的线程函数
void *getElement(void* threadid) {long long tid; // 线程IDtid = (long long)threadid; // 将void*类型的线程ID转换为long型std::cout << tid << std::endl; // 输出线程IDint tmp = TEST_COUNT/NUM_THREADS; // 计算每个线程应该检索的元素数量// 循环检索元素for (int i=tid*tmp, count=0; count<tmp; i++) {count++;skipList.search_element(rand() % TEST_COUNT); // 随机生成一个键，并尝试检索}pthread_exit(NULL); // 退出线程
}int main() {srand(time(NULL)); // 初始化随机数生成器{pthread_t threads[NUM_THREADS]; // 定义线程数组int rc; // 用于接收pthread_create的返回值int i; // 循环计数器auto start = std::chrono::high_resolution_clock::now(); // 开始计时// 创建插入元素的线程for( i = 0; i < NUM_THREADS; i++ ) {std::cout << "main() : creating thread, " << i << std::endl;rc = pthread_create(&threads[i], NULL, insertElement, (void *)i); // 创建线程if (rc) {std::cout << "Error:unable to create thread," << rc << std::endl;exit(-1); // 如果线程创建失败，退出程序}}void *ret; // 用于接收pthread_join的返回值// 等待所有插入线程完成for( i = 0; i < NUM_THREADS; i++ ) {if (pthread_join(threads[i], &ret) != 0 )  {perror("pthread_create() error");exit(3); // 如果线程等待失败，退出程序}}auto finish = std::chrono::high_resolution_clock::now(); // 结束计时std::chrono::duration<double> elapsed = finish - start; // 计算耗时std::cout << "insert elapsed:" << elapsed.count() << std::endl; // 输出插入操作耗时}// 下面的代码块与上面类似，用于创建并管理检索操作的线程{pthread_t threads[NUM_THREADS];int rc;int i;auto start = std::chrono::high_resolution_clock::now();for( i = 0; i < NUM_THREADS; i++ ) {std::cout << "main() : creating thread, " << i << std::endl;rc = pthread_create(&threads[i], NULL, getElement, (void *)i);if (rc) {std::cout << "Error:unable to create thread," << rc << std::endl;exit(-1);}}void *ret;for( i = 0; i < NUM_THREADS; i++ ) {if (pthread_join(threads[i], &ret) != 0 )  {perror("pthread_create() error");exit(3);}}auto finish = std::chrono::high_resolution_clock::now();std::chrono::duration<double> elapsed = finish - start;std::cout << "get elapsed:" << elapsed.count() << std::endl;}pthread_exit(NULL); // 主线程退出return 0;
}

我们还需要新建一个项目工程文件，将之前写的代码重命名成skiplist.h，编译运行进行测试，编译链接要按照如下指令来：

g++ --std=c++11 main.cpp -o stress -pthread

dev_c++里面点进这里修改这个即可。

但在测试过程中，我发现即便是很少的数据量比如4，运行黑框仍旧会卡住，一直无法出来。自己检查代码后才发现，是我在插入数据函数加锁时只在return 0的情况下加了锁，因此在return 1 的情况下，系统就陷入了死锁局面！

加上去之后就好了。

修改后代码如下：

//skiplist.h
#include<stdlib.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <mutex> 
#include <sys/time.h>std::mutex mtx; template<typename K, typename V>
class Node {
private:K key;V val;int node_level;public:Node** forwards;public:Node(K inkey, V value, int level): key(inkey), val(value), node_level(level),forwards(nullptr) {this->forwards = new Node<K, V>*[node_level+1];memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));}~Node(){delete forwards;};K getKey() const {return key;}V get_value() const {return val;}int getLevel() const {return node_level;}void set_value(V value) {val = value;}};template<typename K, typename V>
class SkipList {
private:Node<K,V>* HeadNode = nullptr;int _maxlevel = 0;int temp_level = 0;
public:SkipList(int maxlevel = 500) {_maxlevel = maxlevel;HeadNode = new Node<K, V>(K(),V(),maxlevel);}~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }int getRandomLevel() {srand((int)time(0));int k = 1;while (rand() % 2) {k++;}k = (k < _maxlevel) ? k : _maxlevel;return k;}int insert_element(const K key, const V value) {mtx.lock();int flag = 0;Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode;while (cur) {if (cur->getKey() == key) {flag = 1;cur->set_value(value);}cur = cur->forwards[curlevel]; }curlevel--;}if (flag == 1) {mtx.unlock();return 1;}Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();curlevel = newNode->getLevel();while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() > newNode->getKey()) {prev->forwards[curlevel] = newNode;newNode->forwards[curlevel] = cur;break;} cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}   if (!cur)prev->forwards[curlevel] = newNode;curlevel--;}mtx.unlock();return 0;}bool search_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) return true;cur = cur->forwards[curlevel]; }curlevel--;}return false;}void delete_element(K key) {mtx.lock();Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) {prev->forwards[curlevel] = cur->forwards[curlevel];break;}cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}curlevel--;}mtx.unlock();}void print() {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];std::cout << "Level " << curlevel-1 << ": ";while (cur) {std::cout << cur->getKey() << ":" << cur->get_value() << ';';cur = cur->forwards[curlevel];}std::cout << std::endl;curlevel--;}}void dump_file() {std::ofstream out("D:\\dev_c++\\destination\\out.txt");if (out.is_open()) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {out << cur->getKey() << ":" << cur->get_value() << '\n';cur = cur->forwards[curlevel];}curlevel--;}out.close();}}void load_file() {std::ifstream in("D:\\dev_c++\\destination\\out.txt");char buffer[256];if (!in.is_open()) {std::cout << "open error";} else {while (!in.eof()) {std::string s;in >> s;int index = 0;if (s.size() == 0) return; for (int i = 0; i < s.length(); i++) {if (s[i] == ':') {index = i;break;}}
//                std::cout << s << ' ';std::string s1 = s.substr(0, index);std::string s2 = s.substr(index + 1, s.length() - 1 - index);
//                std::cout << s1 << s2 << std::endl;int key = std::stoi(s1);int value = std::stoi(s2);insert_element(key, value);}}}
};

跳表项目总结

这次完整做完了一个小项目，花了几天。最后才发现测试时会有一些不测试就发现不了的小bug，所以说测试还是蛮重要的。