# SkipList-java

**Repository Path**: TaroYY/SkipList-java

## Basic Information

- **Project Name**: SkipList-java
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-08-09
- **Last Updated**: 2021-10-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 跳表SkipList KV存储引擎 JAVA 实现
本项目就是基于 **跳表** 实现的轻量级键值型存储引擎，使用 **JAVA** 实现。  
实现的功能：  
1. 插入数据（更新数据）
2. 删除数据
3. 查询数据 (是否存在)
4. 数据结构展示
5. 数据落盘
6. 文件加载数据
7. 数据库大小显示。

# JDK 版本
jdk 11  
# 项目中的文件

* pom.xml maven方式创建项目的依赖
* Main.java 小规模测试接口功能的主程序
* SkipList.java 跳表的数据结构实现
* SkipListNode.java 跳表节点的数据结构实现
* StressTest.java 压力测试代码
* SkipListTest.java 测试接口代码
* SkipList.jar 可执行jar文件（运行Main程序）

# 提供接口 （节点CAS版）
* put (插入数据、更新数据) （版本1为 insert，无更新功能）
* delete (删除数据)
* contains (根据键值查询数据是否存在)
* query (根据键值查询数据)
* save (保存跳表)
* load (加载已保存的跳表)
* show (显示跳表)

# 压力测试表现
本项目采用**多线程并发插入、查询数据(ThreadPoolExecutor、CountDownLatch)** 来模拟多个用户同时访问和更改数据库。  
插入数据：这里采取的方式是**随机插入数据(key:Integer,value:String)**，所获取的是**按照对应数据量运行五次取平均**得出的数据。  
查询数据：这里采取的方式是**根据随机 key 值查询数据**的方式，所获取的是**按照对应数据量运行五次取平均**得出的数据。  

不同的并发处理方式效率对比：
## 1. 同步方法 synchronized
### 插入数据
|插入数据规模(万条)|平均树高(层)|平均耗时(s)|QPS|
|---|---|---|---|
|10|16.4|0.3554|281373.10|
|50|18.4|1.4380|347705.15|
|100|19.4|2.9238|342020.66|
|500|22.2|18.0350|277238.70|
|1000|23.2|40.4302|247339.86|
### 查询数据
|插入数据规模(万条)|平均树高(层)|平均耗时(s)|QPS|
|---|---|---|---|
|10|16.4|0.2042|489715.96|
|50|18.4|0.9120|548245.61|
|100|19.4|1.7836|560663.83|
|500|22.2|12.0356|415434.21|
|1000|23.2|28.8008|347212.58|
## 2. 读写锁 ReentrantReadWriteLock
### 插入数据
|插入数据规模(万条)|平均树高(层)|平均耗时(s)|QPS|
|---|---|---|---|
|10|16.6|0.411|243309.00|
|50|18.8|1.7924|278955.59|
|100|20.0|3.8398|260430.23|
|500|21.8|25.1748|198611.31|
|1000|23.0|59.1476|169068.57|
### 查询数据
|插入数据规模(万条)|平均树高(层)|平均耗时(s)|QPS|
|---|---|---|---|
|10|16.6|0.2986|334896.18|
|50|18.8|0.8924|560286.87|
|100|20.0|1.2614|792769.94|
|500|21.8|7.3682|678591.79|
|1000|23.0|18.3672|544448.80|
## 3. 节点CAS
### 插入数据
|插入数据规模(万条)|平均树高(层)|平均耗时(s)|QPS|
|---|---|---|---|
|10|16.4|0.3982|251130.09|
|50|18.4|1.1978|417431.96|
|100|19.6|2.1370|467945.72|
|500|21.6|13.1430|380430.65|
|1000|23.2|33.0160|302883.45|
### 查询数据
|插入数据规模(万条)|平均树高(层)|平均耗时(s)|QPS|
|---|---|---|---|
|10|16.4|0.2262|442086.65|
|50|18.4|0.6648|752105.90|
|100|19.6|1.2590|794281.18|
|500|21.6|7.0334|710893.74|
|1000|23.2|16.9386|590367.56|

# 项目运行方式  
无操作系统限制，只需要安装有jdk 11的运行环境即可运行main程序。
执行命令：
```
java -jar 路径/SkipList.jar
```

# 还能优化的点
* 没有将数据结构打包成jar供别的项目使用
* 可以加上一致性协议，再启动一个http server对外提供分布式存储服务