用Rust从零编写LevelDB

发表于 2024-11-25 更新于 2026-08-18

前言

在现代数据驱动的世界中，对高效且可扩展的数据存储方案的需求前所未有地强烈。键值数据库因其简洁性和卓越性能而备受推崇。对于那些热爱Rust编程并希望构建自己的键值数据库的开发者来说，这本书将是您的理想起点。笔者将引导您一步一步，从零开始，使用Rust设计和实现一个键值数据库。

数据库领域既神秘又充满魅力。正如俗话所说，不亲手实践，就无法深刻理解。通过构建一个键值数据库，我们不仅能深入掌握这类数据库的设计哲学和实现细节，还能借此机会深化对Rust语言的理解和应用。

本书内容围绕一个基于LSM（Log-Structured Merge-tree）的键值数据库设计和实现展开，参考了LevelDB、RocksDB、PebbleDB、AgateDB和BadgerDB等多个成熟数据库的实现。全书示例代码均使用Rust编写，旨在通过实战演练加深读者对Rust特性的理解，同时探索数据库技术的精髓。

LevelDB相较于其他衍生品，虽然没有一些新的论文和工程实践带来的优化，但保留了最初的设计，其相对简单和完整。其他数据库或多或少都能找到LevelDB的影子。

与《Rust编程语言》一书不同，本书不旨在覆盖Rust语言的所有知识点。我们的目标是实现一个键值数据库，因此读者需要具备一定的系统编程基础，例如文件系统相关的读写调用和指针的使用（不仅在unsafe的情况下，有指针的基础也方便理解引用等概念）。这些知识点如果完全讲解清楚会占据很大的篇幅。本书将解释使用到的Rust语法和特性。即使您没有阅读过《Rust编程语言》，也能跟随本书学习Rust的语法。如果您在阅读本书的Rust语法部分遇到困难，可以参考《Rust编程语言》中的相关章节。笔者也是将《Rust编程语言》作为一本参考书反复阅读，并不需要一次性完全读完，书都是常看常新的。

Rust的设计初衷是确保内存安全，避免常见的程序错误，如空指针解引用。其显著特点包括独特的所有权系统、零成本抽象、可靠的错误处理机制以及完善的工具链，使其在系统编程领域尤为突出。

尽管LevelDB是用C++编写的，Rust在某些方面被视为C++的现代替代品。对于那些对C++有深入了解的开发者而言，转向学习Rust应该会相对轻松。然而，Rust提供了与C++不同的编程范式。例如，迭代器和闭包是Rust标准库和语法的一部分，作为语言的核心部分，引入了多种语法糖来支持这些功能，这可能会让熟悉Python的开发者感到亲切。

经典的内存错误包括使用已释放内存的指针、向量长度被修改但另一个引用仍保留原长度信息导致访问不确定内存地址等。Rust的所有权系统在编译阶段就能避免这些问题。

Rust借鉴了函数式编程的多种技巧，为开发者提供了一种既熟悉又新颖的编程体验，例如模式匹配、迭代器、闭包、泛型等。这些特性使得Rust在编写高效、安全和易维护的代码方面具有独特优势。

与有GC的语言相比，Rust可能让使用者感到不适应，许多在其他语言中理所当然的写法在Rust中行不通。Rust对指针的可变性有明确限制，并且只允许存在一个可变引用。这种所有权的检查使编译器变得非常严格，在一定程度上增加了编程的复杂性。然而，这也是Rust的优势之一，它能够在编译阶段发现许多潜在的错误。

相比暴露指针的语言，Rust对内存的解引用有严格的检查。尽管所有权系统有时会让代码显得冗长，但Rust提供了许多有趣的语法和特性，如模式匹配、错误处理宏、默认返回末端表达式等，使得编写Rust代码既轻便又高效。

Rust的性能非常出色，部分Linux内核驱动和Windows安全模块已经采用Rust实现。AWS也在许多地方使用Rust，飞书客户端的一部分代码也使用了Rust，这在一定程度上证明了Rust在系统编程领域的优异表现。如果需要选择一种新语言开发消息队列、数据库、文件系统等软件，Rust是一个非常不错的选择。这也是本书使用Rust实现的原因之一，以展示Rust在这些方面的优势。

在错误处理方面，Rust采用?问号宏简化了传统的错误处理流程，相比Go语言中显式处理错误的if err != nil {}模式是一种进步。这种简洁的错误处理方式不仅提高了代码的可读性，也加速了开发过程。

这些特色贯穿本书始终，在随后的章节中，您将探索到Rust的更多有趣特性。

笔者是一名Rust初学者，里面的很多实现可能存在不正确的写法，欢迎指正。

本书面向的读者

希望通过具体项目深入学习Rust，特别是在键值数据库方面的开发者。
对键值数据库的设计和实现感兴趣的初学者，希望通过实践学习相关内容。
想了解LevelDB架构和实现细节的读者，可以选择性地跳过实现部分进行阅读。

如何阅读和使用代码

本书的第一章主要是讲基础概念例如一些基础的数据结构。第二章开始分部分讲解实现的细节。对于
对Rust比较熟悉的读者可以跳过第一章。

第一章Rust

完整讲解Rust的内容将要消耗大量篇幅，也不是本书的目的。本章节主要介绍在实现过程中会会涉及的一些的语法和特性，让读者在阅读代码的时候没有过多障碍。

数据类型

Rust 是一种静态类型的编程语言，其数据类型可以分为两大类：原始类型（Primitive Types）和复合类型（Compound Types）。以下是 Rust 中常见的数据类型：

原始类型（Primitive Types）

整数类型（Integer Types）：表示整数。有符号整数包括 i8、i16、i32、i64、i128，无符号整数包括 u8、u16、u32、u64、u128。
1
2
let signed_integer: i32 = -42;
let unsigned_integer: u64 = 42;
浮点数类型（Floating-Point Types）：表示小数。Rust 有两个浮点数类型：f32 和 f64。
1
2
let float32: f32 = 3.14;
let float64: f64 = 3.14;
布尔类型（Boolean Type）：表示逻辑值，只有两个可能的值：true 和 false。
1
2
let is_true: bool = true;
let is_false: bool = false;
字符类型（Character Type）：表示单个字符。字符类型使用单引号 '。
1
2
let char_a: char = 'a';
let char_heart: char = '❤';

复合类型（Compound Types）

数组类型（Array Type）：表示固定大小的数组。数组中的所有元素必须拥有相同的数据类型。
1
let array: [i32; 5] = [1, 2, 3, 4, 5];
元组类型（Tuple Type）：表示具有不同数据类型的有序集合。元组的长度是固定的。
1
let tuple: (i32, f64, char) = (42, 3.14, 'a');
切片类型（Slice Type）：表示对数组或其他集合的引用，但没有固定大小。切片是一种动态大小的视图。
1
2
let array: [i32; 5] = [1, 2, 3, 4, 5];
let slice: &[i32] = &array[1..4];
字符串类型（String Type）：表示动态可变的文本字符串。它由 String 类型表示。
1
let my_string: String = String::from("Hello, Rust!");
引用类型（Reference Type）：表示对值的引用。引用在 Rust 中被广泛用于实现借用和所有权系统。
1
2
let original_value: i32 = 42;
let reference: &i32 = &original_value;

这些数据类型提供了灵活性和安全性，通过所有权、借用和生命周期等概念，Rust 的类型系统确保了内存安全和线程安全。在编写 Rust 代码时，正确使用这些数据类型有助于减少运行时错误并提高代码的可维护性。

基本语法

let用于声明变量。

1	let x = 1; // 声明x并赋值为1。

可以使用:显式指定变量类型：

1	let x: i32 = 1;

_表示“存在但不关心”的变量，用于有意忽略某些处理：

// 赋值给一个不需要使用的变量
let _ = 1;
// 忽略函数的返回值
let _ = get_thing();

以_开头的变量表示暂时忽略以避免编译检查，适合在开发过程中使用：

1	let _x = 1;

let可以“覆盖”变量，使之前相同名称的变量失效，且变量类型可以不同：

1
2
3

let x = 1;
let x = 1 + 2;
let x = "str";

Rust也有元组，相当于固定长度的“容器”可以容纳不同的类型，元组可以指定类型。

1
2
3

let pair : (char, i32) = ('a', 17);
pair.0;
pair.1;

元组适用于解构，下面的代码中some_char是'a'，some_int是17。结构也可以使用_忽略全部或者其中一部分。解构也适用于函数的返回值。

let (some_char, some_int) = ('a', 17);
let (_, some_int) = ('a', 17);
let (_, _) = ('a', 17);
let (left, right) = slice.split_at(middle);

{}可以划分作用域，如果使用之前的覆盖规则，可以在内部作用域覆盖外部作用域的变量。

fn main() {
    let x = "out";
    {
        // x = "in" 覆盖了外面的"out"
        let x = "in";
        // 这里会打印"in"
        println!("{}", x);
    }
    // 这里会打印"out"
    println!("{}", x);
}

在Rust中，语块也是表达式。

1
2
3

let x = 42;

let x = { 42 };

语块可以包含多个语句，最后一个不以分号结尾的语句是这个语块的值，否则默认等于()。

let x = {
    let y = 1;
    let z = 2;
    y + z 
};

函数中也有类似的写法。

fn fair_dice_roll() -> i32 {
    return 4;
}

fn fair_dice_roll() -> i32 {
    4
}

if语句也是表达式。

fn fair_dice_roll() -> i32 {
    if feeling_lucky {
        6
    } else {
        4
    }
}

match语句也是表达式。

fn fair_dice_roll() -> i32 {
    match feeling_lucky {
        true => 6,
        false => 4,
    }
}

结构体是用 struct 关键字声明的：

struct Vec2 {
    x: f64, // 64位浮点数，即 "double precision"
    y: f64,
}

它们可以使用结构体字面量初始化，顺序不重要，只有名称重要。：

1 2	let v1 = Vec2 { x: 1.0, y: 3.0 }; let v2 = Vec2 { y: 2.0, x: 4.0 };

还有一种用于从另一个结构体初始化剩余字段的快捷方式，这称为“结构体更新语法”，只能出现在最后位置，并且不能以逗号结束：

let v3 = Vec2 {
    x: 14.0,
    ..v2
};

剩余字段也可以是所有字段，这样就可以复制整个结构体，而不是改变所有权：

1	let v4 = Vec2 { ..v3 };

结构体，像元组一样，可以被解构：

1
2
3

let v = Vec2 { x: 3.0, y: 6.0 };
let Vec2 { x, y } = v;
// `x` 现在是 3.0，`y` 现在是 6.0

下面这种形式可以通过..让v.y会被忽略掉：

1	let Vec2 { x, .. } = v;

let模式可以用作if中的条件：

struct Number {
    odd: bool,
    value: i32,
}

fn main() {
    let one = Number { odd: true, value: 1 };
    let two = Number { odd: false, value: 2 };
    print_number(one);
    print_number(two);
}

fn print_number(n: Number) {
    if let Number { odd: true, value } = n {
        println!("Odd number: {}", value);
    } else if let Number { odd: false, value } = n {
        println!("Even number: {}", value);
    }
}

match 也是一种模式匹配，就像 if let 一样：

fn print_number(n: Number) {
    match n {
        Number { odd: true, value } => println!("Odd number: {}", value),
        Number { odd: false, value } => println!("Even number: {}", value),
    }
}

match 必须是穷尽的：至少有一个分支需要匹配。

fn print_number(n: Number) {
    match n {
        Number { value: 1, .. } => println!("One"),
        Number { value: 2, .. } => println!("Two"),
        Number { value, .. } => println!("{}", value),
        // 如果最后一个分支不存在，我们会得到一个编译时错误
    }
}

如果穷尽匹配很难满足，可以使用 _ 作为 “通配符” 模式：

fn print_number(n: Number) {
    match n.value {
        1 => println!("One"),
        2 => println!("Two"),
        _ => println!("{}", n.value),
    }
}

可以给类型声明方法。

struct Number {
    odd: bool,
    value: i32,
}

impl Number {
    fn is_strictly_positive(self) -> bool {
        self.value > 0
    }
}

变量默认不可以改变。

fn main() {
    let n = Number {
        odd: true,
        value: 17,
    };
    n.odd = false; // 错误：不能对 `n.odd` 赋值，
                   // 因为 `n` 没有被声明为可变的
}

不能被重新赋值

fn main() {
    let n = Number {
        odd: true,
        value: 17,
    };
    n = Number {
        odd: false,
        value: 22,
    }; // 错误：不能对不可变变量 `n` 重新赋值
}

可以使用mut关键字来声明可变变量。

fn main() {
    let mut n = Number {
        odd: true,
        value: 17,
    };
    n.odd = false; // 没问题：`n` 是可变的
}

特征（Traits）在Rust中实现了类似其他语言中的多态功能：

特征定义了一组可以由多种类型共享的行为契约。其定义如下：

1
2
3

trait Signed {
    fn is_strictly_negative(self) -> bool;
}

任何满足这些条件的类型都可以实现这个特征：

impl Signed for Number {
    fn is_strictly_negative(self) -> bool {
        self.value < 0
    }
}

这样，Number 类型就拥有了 is_strictly_negative 方法。特征也可以包含默认实现：

trait Signed {
    fn is_strictly_negative(self) -> bool {
        self.value() < 0
    }

    fn value(&self) -> i32;
}

然后，类型只需要提供那些没有默认实现的方法：

impl Signed for Number {
    fn value(&self) -> i32 {
        self.value
    }
}

Rust 的一个核心特征是 Drop，它允许你定义当值离开作用域时应该发生的事情：

impl Drop for Number {
    fn drop(&mut self) {
        println!("Dropping {}", self.value);
    }
}

当 Number 实例离开作用域时，Rust 会自动调用 drop 方法。

枚举（Enums）允许你定义一个类型，该类型可以是多个不同变体中的一个。这对于值可以有多种但数量有限的类型特别有用：

enum WebEvent {
    PageLoad,
    PageUnload,
    KeyPress(char),
    Paste(String),
    Click { x: i64, y: i64 },
}

与结构体一样，枚举的每个变体可以包含不同类型和数量的数据。你可以使用 match 表达式来操作枚举值：

fn inspect(event: WebEvent) {
    match event {
        WebEvent::PageLoad => println!("page loaded"),
        WebEvent::PageUnload => println!("page unloaded"),
        WebEvent::KeyPress(c) => println!("pressed '{}'", c),
        WebEvent::Paste(s) => println!("pasted \"{}\"", s),
        WebEvent::Click { x, y } => println!("clicked at x={}, y={}", x, y),
    }
}

枚举也可以有方法：

impl WebEvent {
    fn describe(&self) -> String {
        match self {
            WebEvent::PageLoad => String::from("page loaded"),
            WebEvent::PageUnload => String::from("page unloaded"),
            WebEvent::KeyPress(c) => format!("pressed '{}'", c),
            WebEvent::Paste(s) => format!("pasted \"{}\"", s),
            WebEvent::Click { x, y } => format!("clicked at x={}, y={}", x, y),
        }
    }
}

没有返回值的空函数：

1
2
3

fn greet() {
    println!("Hi there!");
}

右箭头表示返回值类型：

1
2
3

fn foo() -> i32 {
    1
}

模块管理

在Rust中，模块是用于组织代码、控制可见性以及支持代码重用的重要概念。Rust的模块系统是基于文件和目录组织的，这使得代码的组织变得清晰而灵活。下面是Rust模块管理的一些关键概念：

模块定义

模块通过mod关键字进行定义，可以在一个Rust文件中定义一个模块。例如：

// 在文件 mod_example.rs 中定义了一个模块
mod example {
    // 模块的内容
}

模块路径

模块路径用于指定模块的位置。Rust使用::来表示模块路径。例如：mod_example::example。

Rust的模块系统与文件系统有很强的映射关系。一个模块可以对应于一个文件，也可以对应于一个目录，包含多个文件。这使得项目的文件和目录结构能够与代码组织一致。

`pub`关键字

在Rust中，使用pub关键字来标识模块、结构体、枚举、函数等的可见性。只有被标记为pub的项才可以在其他模块中被访问。

// 在 example 模块中声明了一个公共的结构体
mod example {
    pub struct MyStruct {
        // 结构体的字段
    }
}
// 在其他模块中使用 example 模块中的 MyStruct
use example::MyStruct;

`mod.rs`文件

文件本身是可以被作为模块引用的，这样可以更好地组织代码。
如果一个模块的内容比较复杂，可以在模块所在的目录中创建一个mod.rs文件，作为模块的“命名空间”，用于存放模块的具体实现。例如：

1
2
3

// 在 example 目录中创建 mod.rs 文件
// example/mod.rs
pub mod sub_module;

使用方式：

1 2	// 在其他模块中引用 example 模块 use example::sub_module;

这个目录用于存放模块的具体实现。这有助于清晰地分离模块的定义和实现。

`crate` 和 `super`

crate关键字用于表示当前crate的根模块，而super关键字用于表示当前模块的父模块。

// 在 crate 根模块中
mod my_module {
    // 在 my_module 中
    mod sub_module {
        // 在 sub_module 中，使用 super 表示 my_module
        use super::super::my_function; // 调用父模块的函数
    }
}

fn my_function() {
    // 函数实现
}

模块的可见性规则

默认情况下，模块和其中的项对外部是不可见的。可以通过pub关键字调整可见性。Rust的模块系统强调了显式性，即除非明确指定为pub，否则默认情况下所有项都是私有的。

pub 有多种用法，包括：

pub：在默认情况下，Rust 中的项是私有的，只能在定义它们的模块中访问。使用 pub 关键字可以将项声明为公共的，使其在整个 crate 中都可见。

pub struct MyStruct {
    pub field: i32,
}

pub fn my_function() {
    // 函数实现
}

在这个例子中，MyStruct 和 my_function 都被声明为公共的，可以在 crate 的任何地方访问。

pub(crate)：限制了项的可见性仅在当前 crate 中。这使得项在 crate 外部是不可见的，但在同一个 crate 内的所有模块都可以访问。

pub(crate) struct InternalStruct {
    // ...
}

pub(crate) fn internal_function() {
    // 函数实现
}

在这个例子中，InternalStruct 和 internal_function 只能在定义它们的 crate 中的任何模块中访问。

pub(super)：限制了项的可见性仅在其父模块（即包含该项的模块）和其父模块的子模块中。

mod parent_module {
    pub(super) struct SuperStruct {
        // ...
    }

    pub fn super_function() {
        // 函数实现
    }

    mod child_module {
        fn inner_function() {
            // 在子模块中可以访问 SuperStruct 和 super_function
            let my_struct = SuperStruct { /* ... */ };
            super_function();
        }
    }
}

在这个例子中，SuperStruct 和 super_function 在 parent_module 中可见，但在 crate 中的其他模块不可见。

pub(self)：限制了项的可见性仅在当前模块中。这使得项对于同一模块中的其他模块是不可见的。

mod my_module {
    pub(self) struct ModuleStruct {
        // ...
    }

    pub(self) fn module_function() {
        // 函数实现
    }

    mod submodule {
        fn inner_function() {
            // 在子模块中不能访问 ModuleStruct 和 module_function
            // 这两个项对于同一模块中的其他模块是不可见的
        }
    }
}

在这个例子中，ModuleStruct 和 module_function 只能在 my_module 中的任何模块中访问。

这些可见性修饰符允许 Rust 程序员精确地控制项的可见性，从而确保代码结构的封装和安全性。

`use`指令

use 指令可用于将其他命名空间的名称 “引入作用域”：

1
2
3

use std::cmp::min;

let least = min(7, 1); // 1

也可以用紧凑的写法：

// 格子单独引入
use std::cmp::min;
use std::cmp::max;
// 从cmp分开
use std::cmp::{min, max};
// 从std分开也可以
use std::{cmp::min, cmp::max};

*可以通配引入：

1	use std::cmp::*;

Rust的模块系统是一个强大的组织和抽象工具，支持创建清晰、可维护、可重用的代码结构。了解和熟练使用模块系统有助于提高代码的可读性和可维护性。

错误类型和可选项

Result 和 Option 是 Rust 中用于错误处理和可选值的两个重要枚举类型。它们在处理不同类型的情况时非常有用。

`Option` 枚举类型

Option 类型用于表示一个值可能存在（Some）或不存在（None）。它通常用于返回一个可能为空的值。

enum Option<T> {
    Some(T),
    None,
}

示例：

fn find_element(vec: &Vec<i32>, index: usize) -> Option<i32> {
    if index < vec.len() {
        Some(vec[index])
    } else {
        None
    }
}

let numbers = vec![1, 2, 3];
match find_element(&numbers, 1) {
    Some(value) => println!("Found: {}", value),
    None => println!("Not found"),
}

`Result` 枚举类型

Result 类型用于表示一个操作可能成功（Ok）或失败（Err）。它通常用于返回一个可能会出错的操作结果。

enum Result<T, E> {
    Ok(T),
    Err(E),
}

示例：

fn divide(a: i32, b: i32) -> Result<i32, String> {
    if b == 0 {
        Err(String::from("Division by zero"))
    } else {
        Ok(a / b)
    }
}

match divide(4, 2) {
    Ok(result) => println!("Result: {}", result),
    Err(e) => println!("Error: {}", e),
}

`Result` 和 `Option` 的关系

Option 用于表示一个值可能存在或不存在，而不涉及错误信息。
Result 用于表示一个操作可能成功或失败，并且可以携带错误信息。

在某些情况下，可以将 Option 转换为 Result，例如在需要提供错误信息时：

fn find_element(vec: &Vec<i32>, index: usize) -> Result<i32, String> {
    match vec.get(index) {
        Some(&value) => Ok(value),
        None => Err(String::from("Index out of bounds")),
    }
}

通过这种方式，可以更灵活地处理错误和可选值。

自定义错误类型

在 Rust 中，通常建议使用自定义的错误类型来更好地表达错误信息。可以通过枚举或结构体来定义自己的错误类型，并实现 std::fmt::Debug 和 std::fmt::Display trait 来提供可读的错误信息。

#[derive(Debug)]
enum MyError {
    DivisionByZero,
    CustomError(String),
}

impl std::fmt::Display for MyError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            MyError::DivisionByZero => write!(f, "Cannot divide by zero"),
            MyError::CustomError(msg) => write!(f, "Custom error: {}", msg),
        }
    }
}

fn divide(a: f64, b: f64) -> Result<f64, MyError> {
    if b == 0.0 {
        Err(MyError::DivisionByZero)
    } else {
        Ok(a / b)
    }
}

fn main() {
    match divide(10.0, 0.0) {
        Ok(result) => println!("Result: {}", result),
        Err(error) => println!("Error: {}", error),
    }
}

使用 `?` 操作符

Rust 中的 ? 操作符可以用于快速地将 Result 或 Option 的值传递给包含错误处理的函数。它简化了错误传播的代码。例如：

fn operation1() -> Result<i32, &'static str> {
    // ...
    Ok(42)
}

fn operation2() -> Result<i32, &'static str> {
    // ...
    Ok(10)
}

fn main() -> Result<(), &'static str> {
    operation1()?;
    operation2()?;
    Ok(())
}

错误处理 thiserror 和 anyhow

错误处理
anyhow提供了统一管理error的方式，任何error都可以存储在anyhow中。
thiserror提供了方便我们定义error的宏。

我们的Result类型都是anyhow::Result并且通过thiserror的宏来自定义错误。

单元测试

通过配置宏 #[cfg(test)]，我们可以指定某个模块为测试模块，并且可以为模块内的函数配置 #[test] 以指定某个函数为测试实例。在 Rust 中，习惯性地会创建一个与模块同级的名为 tests 的模块，然后在该模块中编写测试函数。这些测试代码一般位于与源代码相同的文件中（也可以分成独立的文件编写）。下面的示例代码演示了如何简单验证两个数的相加。在本书中，测试代码按照类似的格式提供，旨在验证实现的正确性，并一定程度上提供对应函数或方法的使用示例。assert_eq! 是一个宏函数，用来断言相等。

// 源代码模块
mod my_module {
    pub fn add(a: i32, b: i32) -> i32 {
        a + b
    }
}

// 测试模块
#[cfg(test)]
mod tests {
    use super::my_module;

    // 测试函数
    #[test]
    fn test_add() {
        assert_eq!(my_module::add(2, 3), 5);
    }
}

本书的代码按章节模块化组织，每个章节都可以独立运行。使用 cargo test 命令，可以按章节前缀运行对应的单元测试（例如 cargo test ch1），也可以执行具体的测试函数（例如 cargo test ch1::skiplist::tests::it_works）。章节内容循序渐进，每章结束时会引入前面章节的模块。这种组织方式使读者能够逐步学习和理解每个模块的工作原理。每个章节相对独立，读者也可以跳跃式阅读。

读者可以根据需要修改每个独立模块，尝试理解其工作原理，或在自己实现过程中参考这些模块。这种结构旨在提供灵活性，使读者能够自由地使用和探索本书的代码。

所有权和引用

所有权是由编译器检查的，因此检查会非常严格。在Rust中，浅拷贝会移交所有权（move），而深拷贝（Copy）则会复制对象，从而避免所有权冲突。如果一个对象实现了Copy trait，也可以进行复制，不会与所有权产生冲突。在Rust中，只有copy和move两种操作。

引用不会获得所有权，因此也没有权利调用Drop。创建引用在Rust中被称为借用，因此借用和引用有时会混用。借用被视为一个动词，而引用被视为一个名词。如果希望在不产生Copy的情况下修改一个对象，可以使用可变引用。

Rust规定一个对象只能有一个可变引用，且不能同时存在其他的可变或不可变引用。

笔者推荐更详细的内容可以阅Rust Book 和
Rust nomicon，这两本书都是比较全面且标准的Rust教程。

在本书的数据库实现中，我们主要使用字节向量和字节切片，分别用 Vec<u8> 和 &[u8] 表示，代表具有所有权的字节块和对字节块的借用。由于所有权的关系，如果我们只需要读取数据，会使用借用；如果需要保存写入的数据，则会使用具有所有权的对象 Vec<u8>。&mut [u8] 是可修改的借用，实际上也具有所有权，当我们需要修改连续内存的一部分时，可以使用这种类型。

如果我们不需要所有权，as_ref 和 as_mut 可以为我们提供相应的引用。

Rust约定的迭代器类型如下，注意 IntoIter 有些不同，如果是一个切片的 IntoIter，返回的仍然是引用。

1
2
3

IntoIter - T
IterMut - &mut T
Iter - &T

而 as_deref 和 as_deref_mut 可以帮助我们自动解多层引用。

避免盲目使用 `.clone()` 满足借用规则

借用检查器确保 Rust 用户在开发中不会产生不安全的代码。具体而言，它防止了两种情况：首先，只允许存在一个可变引用；其次，允许存在多个引用，但全部都是不可变引用。如果编写的代码不符合这些条件，当开发人员通过克隆变量来解决编译器错误时，就可能陷入这种反模式。

对于初学者而言，使用 .clone() 来解决借用检查器引起的混乱问题是很诱人的。然而，这样做会带来严重的后果。使用 .clone() 会导致数据的复制，两者之间的任何更改都不会同步，就像存在两个完全独立的变量一样。

有一些特殊情况，例如 Rc<T> 被设计成可以智能处理克隆。它在内部管理数据的精确一份拷贝，克隆它将只克隆引用。

还有 Arc<T>，它提供对在堆上分配的类型为 T 的值的共享所有权。在 Arc 上调用 .clone() 会产生一个新的 Arc 实例，它指向堆上与源 Arc 相同的分配，同时增加引用计数。

总的来说，克隆应该是经过深思熟虑的，要充分了解后果。如果使用克隆来消除借用检查器错误，这是可能正在使用这种反模式的一个很好的指示。

即使 .clone() 是一个糟糕模式的指示，有时写效率低下的代码也是可以接受的，比如：

开发者仍然是个新手
代码没有很大的速度或内存约束（比如黑客马拉松项目或原型）
满足借用检查器真的很复杂，而你更愿意优化可读性而不是性能

如果怀疑存在不必要的克隆，应该充分了解《Rust Book》关于所有权的章节，然后评估是否需要这个克隆。

同时，务必在项目中始终运行 cargo clippy，这个 lint 工具会帮你检查一些不必要的 clone。

函数借用参数的选择

函数参数会用到大量的借用，因为借用不会产生拷贝，但在使用借用的时候尽量使用直接的借用类型 &str、&[T]、&T 而不是 &String、&Vec<T>、&Box<T>。在作为参数的时候，后面的拥有所有权的类型（智能指针）可以自动转换成前面的类型，而反过来则不可以。例如，下面这个函数如果把参数改成 &String 是无法编译的。原因是直接的引用类型需要再分配一个对应的所有权类型才能和所有权类型的引用对齐，但是反过来进行一次解引用就可以获得直接引用。比如 a = Box<T>，其实相当于 &(*a)，编译器自动进行了转化先解引用对应的直接类型然后直接引用。反过来的话 a = &T，那就得 &Box::new(*a)，需要多创建这个 Box 对象，编译器就直接拒绝了。

fn demo(word: &str) {
}

fn main() {
    let ferris = "Ferris";
    let curious = "Curious".to_string();
    demo(ferris);
    demo(&curious);
}

不可变引用和 Rc

不可变引用的生命周期必须小于所有权的生命周期，但Rc不要求，只要最后一个引用离开生命周期则回收。

临时的可变性

可以将可修改对象重新赋值让可变性消失。这样做有一个好处就是如果你明确在之后不想修改该对象，而又人为（可能被合作者，或者两个月后的自己）错误地修改了，编译器就会帮你检查出来。我觉得更多的是在人的“阅读期”直观地明确代码的可变性。

let data = {
    let mut data = get_vec();
    data.sort();
    data
};
// data 是可变的。

let mut data = get_vec();
data.sort();
let data = data;

// data 是不可变的。

协同性

协同性是Rust里面最难的部分了。

//fn two_cell_refs<'big: 'small, 'small>(
//    // NOTE: these two lines changed
//    big: Cell<&'big u32>,
//    small: Cell<&'small u32>,
//) {
//    assign(big, small);
//}

//  如果让mut reference扩大生命周期就会导致垂悬指针。
//  Vec可以是因为Vec是有所有权的，所以不会出现垂悬指针。
fn two_refs<'big: 'small, 'small>(big: Vec<&'big u32>, small: Vec<&'small u32>) {
    take_two(big, small);
}
fn take_two<T>(_val1: T, _val2: T) {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_works() {
        let skl = SkipList { head: None };
    }
}

NonNull本质是一个*const T，从而使得NonNull可以与T协变，通过强制转换的方式让这个指针是可修改的。这是标准库中常用的一个对象，目的是让Vec这样的类型使用起来与T具有协变性。

1
2
3

pub struct NonNull<T> {
    pointer: *const T,
}

具体的解释可以参考这里，目前笔者也没有完全理解这个概念。

Subtyping is the idea that one type can be used in place of another.

范型

Rust 中的泛型是一种强大的特性，它允许你编写适用于多种数据类型的代码，同时保持类型安全。通过泛型，可以编写更加灵活、抽象和可重用的代码，同时保持 Rust 的内存安全和零成本抽象。

以下是 Rust 中泛型的一些关键概念和用法：

泛型函数

在 Rust 中，你可以编写泛型函数，使其适用于多种类型。示例：

fn print_twice<T>(value: T) {
    println!("{:?}", value);
    println!("{:?}", value);
}

fn main() {
    print_twice("Hello, Rust!");
    print_twice(42);
}

在这个例子中，print_twice 是一个泛型函数，可以接受任意类型的参数，并执行相同的打印操作。

泛型结构体

可以为结构体定义泛型类型参数，以实现对不同类型的结构体的抽象。示例：

struct Point<T> {
    x: T,
    y: T,
}

fn main() {
    let int_point = Point { x: 1, y: 2 };
    let float_point = Point { x: 1.5, y: 2.5 };
}

在这个例子中，Point 结构体可以用于包含任何相同类型的坐标点。

泛型枚举

枚举也可以包含泛型类型参数，以增加其灵活性。示例：

enum Result<T, E> {
    Ok(T),
    Err(E),
}

fn main() {
    let success: Result<i32, &str> = Result::Ok(42);
    let failure: Result<i32, &str> = Result::Err("Error message");
}

在这个例子中，Result 枚举表示可能包含成功结果（Ok）或错误信息（Err），并分别包含了两个泛型类型参数。

泛型实现

可以对泛型类型实现 trait，以为多种类型提供相同的行为。示例：

trait Printable {
    fn print(&self);
}

impl<T: std::fmt::Debug> Printable for T {
    fn print(&self) {
        println!("{:?}", self);
    }
}

fn main() {
    "Hello, Rust!".print();
    42.print();
}

在这个例子中，Printable trait 定义了一个 print 方法，然后对所有实现了 Debug trait 的类型实现了这个 trait。

Rust 的泛型提供了强大的抽象能力，帮助编写更加灵活和通用的代码。通过泛型，你能够在不失去类型安全的前提下，减少代码的冗余并提高代码的可维护性。

Read 和 Write

在本书中用的 Trait 比较多的是 Read、Write 和 Seek。

在 Rust 中，Read、Write 和 Seek 是三个与 I/O 操作密切相关的 trait，它们为实现输入和输出操作提供了通用的接口。这三个 trait 可以用于文件、网络套接字等不同的数据源和目标。

Read Trait：
Read trait 定义了用于从数据源读取字节的方法。它主要包含一个方法：

1	fn read(&mut self, buf: &mut [u8]) -> Result<usize, Error>;

这个方法从实现 Read trait 的类型中读取字节，并将它们存储到提供的缓冲区 buf 中。方法返回一个 Result，其中 Ok(n) 表示成功读取了 n 个字节，Err 表示发生了错误。

Write Trait：
Write trait 定义了用于将字节写入数据目标的方法。它主要包含一个方法：

1	fn write(&mut self, buf: &[u8]) -> Result<usize, Error>;

这个方法将提供的缓冲区 buf 中的字节写入到实现 Write trait 的类型中。方法同样返回一个 Result，其中 Ok(n) 表示成功写入了 n 个字节，Err 表示发生了错误。

Seek Trait：
Seek trait 定义了用于在数据源中定位和移动读写指针的方法。它包含三个方法：

1
2
3

fn seek(&mut self, pos: SeekFrom) -> Result<u64, Error>;
fn stream_len(&mut self) -> Result<u64, Error>;
fn stream_position(&mut self) -> Result<u64, Error>;

seek 方法通过给定的 SeekFrom 枚举类型，将读写指针移动到指定位置。
stream_len 方法返回数据源的总长度。
stream_position 方法返回当前读写指针的位置。

SeekFrom 枚举有以下几种可能的值：

SeekFrom::Start(n)：将指针设置到数据源的起始位置加上 n。
SeekFrom::End(n)：将指针设置到数据源的末尾位置加上 n。
SeekFrom::Current(n)：将指针从当前位置移动 n 个字节。

这些 trait 为实现了文件、内存缓冲区等不同类型的数据源和目标提供了通用的接口，使得可以方便地使用相同的 I/O 操作代码处理各种类型的输入输出。在标准库中，例如 File 和 BufReader 都实现了这些 trait，使得对文件和缓冲区的读写变得简单和灵活。

本书中会大量用到这些 Trait，因为 Vec<u8> 和 fs::File 都实现了这个接口。

Iterator

Iterator用于不可变迭代，IntoIterator用于获取所有权并进行迭代，MutIterator用于可变迭代。
在每个示例中，我们都使用了不同的方法进行迭代，并根据需要进行所有权的转移或可变引用的修改。
Iterator的实现，多种iterator的惯例，
Rust要求所有的集合数据类型都要有如下的迭代器，会返回上述方法。

1
2
3

fn iter(&'a self) -> Items<'a>;
fn into_iter(self) -> ItemsMove;
fn iter_mut(&'a mut self) -> ItemsMut<'a>;

Rust 的标准库为集合类型提供了一组通用的迭代方法，这些方法通常以 Iterator trait 的形式提供。这些方法通常分为三类，即标准的迭代方法 trio：

fn iter(&'a self) -> Items<'a>; 用来遍历&T。

这个方法返回一个不可变的迭代器，允许对集合中的元素进行只读的迭代。返回的 Items 类型是一个迭代器对象，其生命周期与集合本身相同，保证迭代器不会在集合被销毁前失效。

fn iter_mut(&'a mut self) -> ItemsMut<'a>; 用来遍历&mut T

这个方法返回一个可变的迭代器，允许对集合中的元素进行修改。返回的 ItemsMut 类型是一个可变迭代器对象，其生命周期与可变引用的生命周期相同，确保迭代器不会在可变引用结束后继续使用。

fn into_iter(self) -> ItemsMove; 用来遍历T，但如果T是一个引用类型其实和iter是类似的。

这个方法获取集合的所有权并返回一个拥有所有权的迭代器。这表示集合本身将不再可用，因为它的所有权已经转移到迭代器上。返回的 ItemsMove 类型是一个拥有所有权的迭代器对象。

为了提供更大的灵活性和符合 Rust 的所有权模型，这些方法还要求集合类型和对集合的（可变）引用都实现了 IntoIterator trait。这个 trait 提供了一个统一的方式，使得集合类型和引用都能够被用于 for 循环等需要迭代的上下文中。

这种设计使得 Rust 中的迭代更为一致和灵活，同时确保了在迭代过程中对所有权和可变性的严格控制。

两级迭代器（TwoLevelIterator）可以使用标准库的flat_map可以把两级迭代器展开成一个大的迭代器，适用于一些多层次迭代器的场景。

fn main() {
    let data = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];

    let flat_iter = data.iter().flat_map(|inner| inner.iter());

    for &num in flat_iter {
        println!("{}", num);
    }
}

归并迭代器可以实现两个有序迭代器的归并排序

struct MergeSortIterator<L, R>
where
    L: Iterator,
    R: Iterator<Item = L::Item>,
{
    left: L,
    right: R,
    left_value: Option<L::Item>,
    right_value: Option<R::Item>,
}

impl<L, R> MergeSortIterator<L, R>
where
    L: Iterator,
    R: Iterator<Item = L::Item>,
{
    fn new(left: L, right: R) -> Self {
        let mut sorter = MergeSortIterator {
            left,
            right,
            left_value: None,
            right_value: None,
        };

        sorter.fetch_values();
        sorter
    }

    fn fetch_values(&mut self) {
        self.left_value = self.left.next();
        self.right_value = self.right.next();
    }
}

impl<L, R> Iterator for MergeSortIterator<L, R>
where
    L: Iterator,
    R: Iterator<Item = L::Item>,
    L::Item: Ord,
{
    type Item = L::Item;

    fn next(&mut self) -> Option<Self::Item> {
        match (self.left_value.take(), self.right_value.take()) {
            (Some(left), Some(right)) => {
                if left <= right {
                    self.left_value = self.left.next();
                    self.right_value = Some(right);
                    Some(left)
                } else {
                    self.left_value = Some(left);
                    self.right_value = self.right.next();
                    Some(right)
                }
            }
            (Some(left), None) => {
                self.left_value = self.left.next();
                Some(left)
            }
            (None, Some(right)) => {
                self.right_value = self.right.next();
                Some(right)
            }
            (None, None) => None,
        }
    }
}



fn main() {
    let iter1 = vec![1, 3, 5, 7, 9].into_iter();
    let iter2 = vec![10,11, 12, 13, 14].into_iter();

    let merge_iter = MergeSortIterator::new(iter1, iter2);

    for item in merge_iter {
        println!("{}", item);
    }
}

幽灵数据

如果SkipIterator使用&'a Link很奇怪，因为Link本身就是个Rc
在引用为0的时候回收，不需要生命周期的标记，但如果不用的话编译器会报错。
我们希望持有SkipNode的引用，生命周期应该和SkipNode一致，所以引入
幽灵数据，标记我们逻辑上关联的对象，因为结构体中没法引用这个类型。

struct SkipIterator<'a> {  
    head: Link,
    marker: PhantomData<&'a SkipNode>,
}

impl<'a> Iterator for SkipIterator<'a> {
    type Item = &'a SkipNode;
    fn next(&mut self) -> Option<Self::Item> {
        None
    }

}

性能调优

TODO

perf profile

tracing

第二章理解键值数据库

键值数据库的介绍

键值数据库（Key-Value Database）在NoSQL（非关系型数据库）范畴中占据重要地位，其采用简洁的键值的结构对数据对象进行存储和检索。
每个数据项由键（key）和关联的值（value）组成，类似于字典或哈希表的数据模型，其中键是唯一标识符，而值则是与之关联的数据。这种简单的键值对模型使得键值数据库在存储和检索简单数据时表现出色。

许多键值数据库支持分布式架构，能够在多个节点上存储数据，以提高性能和可靠性。亚马逊的DynamoDB是一个典型的例子，于1999年提出并成为高度可扩展的键值数据库系统，满足了亚马逊的分布式存储需求，其思想和设计对后来的键值数据库系统产生了深远的影响。

Redis是另一备受欢迎的键值数据库，由Salvatore Sanfilippo于2009年创建。它是一种开源的内存中数据结构存储系统，支持多种数据结构，包括字符串、哈希表和列表，因而成为广泛使用的键值数据库。

LevelDB是由Google开发的高性能键值数据库，采用LSM树（Log-Structured Merge Tree）的结构。在2012年，RocksDB发布，进一步优化了性能和存储效率，受到了广泛的应用。

键值数据库以其快速的读写性能而著称，尤其在需要快速检索特定键的情境下表现出众。它们通常具备横向可扩展性，能够通过添加更多节点来处理更大的负载。其对值的数据结构没有强制规定，因此可以灵活存储各种类型的数据。本书聚焦于单机键值数据库，不会涉及一些集群数据库相关的分布式能力和扩展能力。

LSM

本书将会实现一个类似LevelDB的键值数据库，其核心数据结构是LSM（Log-Structured Merge Tree）。

LSM最早来源于1996年的一篇论文[^1]，而被广为人知的契机则是Google的BigTable[^2]论文，其中的文件格式基于LSM。Google开源了类似键值数据库的单机版本，即LevelDB[^3]。传统数据库通常使用B-Tree类的数据结构，它具有许多优点。随着LevelDB的诞生，基于LSM-Tree的数据结构也逐渐进入人们的视野。

LSM是一种用于存储和管理大规模键值对数据的数据结构，它在特定应用场景中非常有效，具有以下优势：

高写入吞吐量：LSM树通过将写入操作追加到顺序写的文件中，并使用内存和磁盘两级存储结构，实现了高效的写入吞吐量。写入操作可以在内存中迅速完成，然后异步地合并到磁盘上的存储文件中。
压缩和合并：LSM树通过定期合并和压缩磁盘上的存储文件，提高了读取性能。这些合并操作使得数据在磁盘上以更为紧凑的形式存储，减少了读取时需要扫描的数据量。
高吞吐读取：LSM树的结构使得范围查询更加高效，因为数据在磁盘上以顺序方式存储。这对于分析型工作负载非常有利。
容错性：由于LSM树的写入操作是追加到预写日志文件中的，这提供了一种容错机制。即使在写入过程中出现故障，系统也可以通过重新应用日志来恢复。
可扩展性：LSM树适用于大规模的分布式存储系统，支持数据的水平扩展。各个节点可以独立地执行写入和合并操作，从而提高了系统的可扩展性。
减少随机I/O：LSM树的追加写入方式减少了磁盘上的随机I/O，有助于提高写入性能。这对于使用磁盘作为主要存储介质的系统尤为重要。

[^1]: 《The Log-Structured Merge-Tree (LSM-Tree)》：这是LSM的原始论文。
[^2]: 《Bigtable: A Distributed Storage System for Structured Data》（作者：Fay Chang等）：这是Google的Bigtable论文，该文档介绍了Bigtable如何使用LSM树来管理大规模分布式数据存储。
[^3]: 《LevelDB: A Fast Persistent Key-Value Store》（作者：Jeff Dean, Sanjay Ghemawat）：这是Google开发的LevelDB的论文，该数据库使用了LSM树结构。论文提供了对LSM树及其在LevelDB中的应用的深入了解。

HDD和SSD

LevelDB是为了针对HDD的追加写的特性而设计的，有很多优化是基于SSD的。
有一本书关于SSD的《深入浅出SSD》详细阐述了SSD的特性。

第三章构建数据库引擎

基本架构

整个数据库的基本架构下图，一般来说，一个实现LSM键值存储接口所使用的对象是任意字节流。
作为搜索结构，所有数据会有序排列在存储中，常用的操作有插入、更新、获取、遍历和删除等。
为了利用追加写的特性，其中的删除一般是通过插入“墓碑”来代替而不会真正的删除，
而更新则是追加一个键的新版本，所以整个数据库只用到了追加写不使用随机写，充分利用
机械硬盘的追加写性能远远高于随机写的特性。机械硬盘在写之前需要进行磁片上的寻址操作，
这导致随机写相较于顺序写多了很多寻址操作，其之间的性能大致差了100倍。

用到这追加写的文件就是预写日志。可靠的单机数据库需要确保用户调用写入接口返回成功后，即使进程重启（甚至因机器宕机而中断）也不会导致数据丢失。
采用预写式日志是数据库中常见的一种手段，数据会按照先写内存再到日志的顺序进行更新。
由于数据已经持久保存在磁盘上，即使发生异常，内存数据丢失，也能够通过重放预写日志确保数据的完整性。
当前的预写式日志文件会在内存的形式一般叫MemTable。
很多数据库中writer_buffer相关的配置指的就是这个MemTable的大小，因为某种程度上它就是预写日志的内存缓存。

当MemTable达到容量上限（大多数数据库的默认设置为4KB），内存表的内容会被保存在持久化的文件存储中，接着日志文件可以安全删除。
这个表在文件系统上的形式是一个不可更改的搜索结构，一般会用SST（Static Sorted Table），顾名思义就是不可更改的、有序的文件结构。
该文件的不可更改的特性很像Rust变量默认的immutable。内存数据结构需要满足高效的查找和插入，其底层的数据结构一般用SkipList来实现。

数据库会对SSTable进行分层合并，由上层（或上上层）的SSTable合并成新的SSTable，并写入到下一层。
这个过程被称为major compact。因此，层数越小，数据越新，层数越大，数据越久远。

为了限制内存大小，当MemTable达到一定大小后，会转换为不可变内存表。
会作为整个数据库的第0层的SStable，是比较特殊的一层，这个合并过程称为minor compact。LevelDB的由来正是这种分层合并的结构。

当有新的文件产生时需要一个清单文件对这些文件进行记录，一般会使用一个叫MANIFEST的文件保存，用于记录各阶段文件集合信息。
为了更快速的查找，可能还会记录一些附加信息，例如文件大小、最大最小key等。这个文件相当于保存了所有在持久化存储上的SStable的元信息。

对于读操作，需要从内存表、不可变内存表、level-0 SSTable里查找，然后再从level 1中的文件开始查找。

MemTable

MemTable是一个内存中的数据结构，在数据被刷新到SST文件之前保存它们。它相当于一个读写的缓存——新的写总是将数据插入到MemTable中，而读必须在从SST文件读取之前查询MemTable，因为MemTable中的数据是较新的。一旦内存表被填满，它就变成不可变的，并被一个新的内存表所取代。一个后台线程将MemTable的内容刷新到一个SST文件中，之后MemTable就可以被销毁了。MemTable的大小一般是64MB。

SkipList

SkipList（跳表）是一种常用于实现有序存储的数据结构，通常用于构建内存表（MemTable）等应用场景。相比于平衡树等结构，SkipList 不需要复杂的旋转调整来保持平衡，其实现较为简单且易于理解。

SkipList 由一系列节点组成，每个节点包含键值对以及多个层级的指针。节点的高度由一个概率随机决定，这使得 SkipList 在期望上具有 O(log n) 的搜索复杂度。节点结构如下：

struct SkipNode {
    key: Vec<u8>,
    value: Vec<u8>,
    h: usize,
    next: Vec<Link>,
}

SkipList的搜索操作是SkipList中的基本操作之一。从头节点开始，逐层向下搜索，如果找到等于目标键的节点，则返回对应值；如果找到大于目标键的节点，就下移一层继续搜索；如果找到小于目标键的节点，就向右移动。这样，通过多层级的指针，可以有效地减少搜索路径。
但是skip list的常数项相对小很多。skip list在空间上也比较节省。一个节点平均只需要1.333个指针（甚至更少），并且不需要存储保持平衡的变量。

对于层级链表，每增加一层链表，节点的搜索路径就会减半，提高搜索效率。以下是一个示例，展示了如何通过层级链表来降低搜索时间复杂度。
对于一个链表来说，搜索的时间复杂度是O(n)的，搜索5需要5次（1，2，3，4，5）。

1	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

这个搜索是线性的，但是如果再加一个链表，每隔一个结点取一次，可以节省一半的时间，从最高level的链表开始到小于后置节点时向下一个level搜索，这时5要搜索4次（1，3，5），找到4需要3次（1，3，4）。

1 2	1 - - - - 3 - - - - 5 - - - - 7 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

以此类推，再增加一个链表的话，此时5只要搜索2次（1，5），4则没变还是3次（1，3，4）。

1
2
3

1 - - - - - - - - - 5 - - - - - 
1 - - - - 3 - - - - 5 - - - - 7
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

这里每个节点的元素只需要存一次，但是每个节点的高度之内都要保存对应指针。

SkipList相较于一些有序数据结构比如平衡树来说不需要做一些旋转的调整来保持树的平衡，节点的高度是基于概率的，如果设置概率为1/2的话可以通俗的理解为“丢硬币，每次正面则这个节点的高度提高一层”，从期望上来说是可以被证明为log(n)的。因为SkipList和链表很接近，相较于平衡树来说手写更容易实现。但不巧的是链表在Rust里面是地狱难度的实现，本章的篇幅因此会比较长。

前言