/SkipList

数据结构之跳表

Primary LanguageC++

数据结构之跳表

说明

  • 实现了跳表这一个数据结构,其中参考程序员卡尔跳表项目并且修改了一部分内容

  • 实现跳表的增删改查 、持久化到文件、缓存、重载[]操作运算符达到stl中map[key]=value的功能。

  • 利用指向指针数组的指针以及RAII**等进行跳表的维护

  • 注意:跳表目前的模板类型目前只支持int,char,string,bool,long long类型,否则部分功能不能用

  • 若是自定义类型,需要传入比较函数,

  • 若是含有==和!=需要进行重载,那么需要自行封装跳表的重载函数

  • 持久化文件的io操作需传入自定义类型以及字符串转换规则,因为在文件系统中,默认将所有数据类型转化为string类型作为中间类型,(若是未提供该类型的话)需要自定义转换函数

压力测试

在随机写读情况下,该项目每秒可处理啊请求数(QPS): 24.39w,每秒可处理读请求数(QPS): 18.41w

项目运行方式

首先将代码拉取到本地,并且将对应目录切换到当前项目目录下 输入以下命令

make
./skip

个人笔记

对应个人笔记链接如下(包含自身对跳表的理解) https://www.yuque.com/huanxin-katrm/yybn77/mqt9itnbc4v6ih4k?singleDoc# 《分布式存储之跳表项目》