引言

TinyDB 支持多种插件用于功能扩展，比如 tinyindex 插件用于实现文档索引。

本文基于 tinyindex 插件简单介绍索引的原理与实现。

tinyindex

介绍

tinyindex 插件实现文档索引，尽管支持更新操作，不过由于基于有序数组实现，因此更适用于存储静态数据。

Document indexing for TinyDB. Basically ensures deterministic (as long as there aren’t any changes to the table) yielding of documents.

tinyindex 的代码很简单，不到40行，但麻雀虽小五脏俱全，有助于更好的理解索引的作用。

此外，还提供了50行左右的测试方法。

使用

tinyindex 中分别实现了基于单个字段与多个字段的索引，下面分别使用这两种索引。

index_test 函数中创建单字段索引，然后按下标访问。

def index_test():
    table = db.table('tb')
    table.insert_multiple([
        {'k': i} for i in [4, 2, 1, 3, 5]
    ])

    idx = index.Index(table, "k")
    # {'k': 1}
    print(idx[0])

分别打印原始数据与索引数据，可以看到索引有序。

raw:  [{'k': 4}, {'k': 2}, {'k': 1}, {'k': 3}, {'k': 5}]
index: [{'k': 1}, {'k': 2}, {'k': 3}, {'k': 4}, {'k': 5}]

multi_index_test 函数中创建多字段索引，然后同样按下标访问。

def multi_index_test():
    table = db.table('tb')
    pairs = [
            [1, 2],
            [2, 3],
            [2, 4],
            [3, 1],
            [3, 5],
        ]
    shuffle(pairs)
    table.insert_multiple([
        {'k': k, 't': t} for k, t in pairs
    ])

    idx = index.Index(table, "k", "t")
    assert [d['k'] for d in idx] == [1, 2, 2, 3, 3]
    assert [d['t'] for d in idx] == [2, 3, 4, 1, 5]
    # {'k': 1, 't': 2}
    print(idx[0])

分别打印原始数据与索引数据，可以看到索引多字段排序。

raw:  [{'k': 2, 't': 3}, {'k': 3, 't': 1}, {'k': 1, 't': 2}, {'k': 3, 't': 5}, {'k': 2, 't': 4}]
index: [{'k': 1, 't': 2}, {'k': 2, 't': 3}, {'k': 2, 't': 4}, {'k': 3, 't': 1}, {'k': 3, 't': 5}]

其中，两条 assert 语句都没有抛出异常，表明第一个字段有序，第二个字段无序，只有当第一个字段相同时第二个字段有序。

 idx = index.Index(table, "k", "t")
    assert [d['k'] for d in idx] == [1, 2, 2, 3, 3]  # 有序
    assert [d['t'] for d in idx] == [2, 3, 4, 1, 5]  # 无序

那么，tinyindex 中索引的数据结构是什么，当数据更新时索引也会自动更新吗？

实现

Index

首先，tinyindex 中索引的数据结构是有序数组。

索引对象的创建语句如下所示，实际上就是 Index 类的实例化。

idx = index.Index(table, "k")

从源码中可以看到，Index 类的构造方法中仅保存相关数据，包括表、字段与排序规则。

class Index(object):
    def __init__(self, table, *keys, **kwargs):
        self.table = table
        self.keys = keys
        self.reverse = bool(kwargs.get('reverse'))

从索引的构造方法中可以看到索引针对的表级别。

那么，什么时候创建顺序数组呢？

实际上，在读取索引时才会实时创建顺序数组作为索引，如下所示。

print(idx[0])

Index 类中实现了__getitem__方法， 因此支持 [] 运算符访问，其中调用 ranked 方法创建索引。

    def __getitem__(self, idx):
        return self.ranked()[idx]

ranked

ranked 方法中创建顺序数组，其中调用 list.sort 方法根据指定字段与排序规则进行原地排序，因此该方法没有返回值。

    def ranked(self):
        records = list(self.all())
        records.sort(
            key=self.keyfunc,
            reverse=self.reverse,
        )
        return records

其中调用的 all 方法是一个生成器函数，其中每条数据都会调用 can_index 方法判断是否可以索引。

    def all(self):
        for item in self.table.all():
            if self.can_index(item):
                yield item

can_index 方法中判断数据是否可以索引的方法比较简单，只对有该字段的数据创建索引，类似于 MongoDB 中的稀疏索引。

    def can_index(self, datum):
        return all(key in datum for key in self.keys)

原因是 tinydb 与 MongoDB 中都没有固定的表结构，因此每条记录包含的字段可能不一致。

从 list.sort 的调用方式可以看到 tinyindex 支持以下两个特性：

• 不仅支持单列索引，还支持多列索引；
• 不仅支持顺序索引，还支持逆序索引。

list.sort 方法中指定的排序函数 keyfunc 是一个嵌套函数，内部函数 function 的入参 datum 由 list.sort 传入。该函数的作用是从指定记录中取出与索引有关的字段，并按照顺序封装为元组，元组类型有序不可变。

    @property
    def keyfunc(self):
        def function(datum):
            return tuple(datum[k] for k in self.keys)
        return function

有了索引以后，访问指定数据时就不再需要调用 read() 方法读取磁盘文件。

tables = self._storage.read()

此外，由于在读取索引时才会实时创建顺序数组，因此当数据更新时索引也会自动更新。

# [{'k': 4}, {'k': 2}, {'k': 1}, {'k': 3}, {'k': 5}]
idx = index.Index(table, "k")
# {'k': 1}
print(idx[0])
table.update({'k': 8}, Query().k == 1)
# {'k': 2}
print(idx[0])

索引

数据结构

索引是用于优化数据查询操作的数据结构，这些数据结构通过某种方式指向数据，可以快速定位原始数据。

比如索引中保存数据对应的物理地址，没索引时全表扫描，有索引时可以直接访问相应的数据。

索引的优点是通过降低磁盘 IO 次数加速查询。缺点是占用内存或磁盘空间，同时减慢了插入与更新操作的速度。

不同的数据结构实现索引时对应不同的优缺点，常见的数据结构包括：

• 哈希表，基于键值对访问数据。原理是通过散列函数将 key 转换成一个固定的地址，然后将 value 存储在该位置，如果发生哈希碰撞就在该位置拉出一个链表。优点是插入速度快，根据 key 直接追加写入，缺点是散列函数处理后的 key 无序。因此适用于等值查询（如缓存），不适用于范围查询；

• 有序数组，基于下标访问数据。原理是二分查找，时间复杂度为 O(logN)。优点是等值查询与范围查询效率高，缺点是更新时需要移动数据，因此只适用于存储静态数据，如很少变动过的配置数据或历史数据。相比于数组，链表的优点是更新时不需要移动数据，缺点是内存不连续，查询效率低，每次都需要遍历链表。而数组中顺序一致的记录在文件中也是顺序存储的，因此可以一次读取多个数据块；

• 二叉搜索树，原理是父节点左子树的所有节点的值小于根结点，右子树所有节点的值大于根结点。优点是既有链表的快速插入与删除操作的特点，又有数组快速查找的优势，时间复杂度均为O(logN)，类似二分法。缺点是不平衡，当根结点是最小值或最大值时，二叉搜索树将完全退化成线性结构；

• ALV 树：严格的平衡二叉树，所有结点的左右子树高度差不超过1，插入与删除操作时需要通过旋转来保持平衡，一般用平衡因子差值判断是否平衡并通过旋转来实现平衡。由于旋转非常耗时，因此 ALV 树适合用于插入删除操作较少、查找较多的情况。ALV 树在 Windowd NT 内核中应用广泛；

• 红黑树：弱平衡二叉树，在每一个结点上增加一个存储位表示结点的颜色，可以是红色或黑色。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树可以确保没有一条路径会比其他路径长出两倍。相比于严 ALV 树，红黑树旋转次数减少，但是树的高度增加。因此对于查找、插入与删除操作多的情况下，可以使用红黑树。如 IO 多路复用 epoll 的实现采用红黑树组织管理 sockfd，以支持快速的增删改查；

• B- 树，多路平衡查找树，其中 B 可以理解为 Balance。MySQL 用磁盘 IO 次数衡量查询效率，而磁盘 IO 次数往往由树的高度决定。在大规模数据存储时，ALV 树或者红黑树往往出现由于树的高度过大导致磁盘 IO 频繁造成性能降低，因此二者基本都是在存储在内存中才会使用的数据结构。B- 树是多路树，因此树的高度低。通常出度是非常大的数字，通常超过 100，通常是 1200，高度不超过 3。缺点是数据保存在每一个节点中，而磁盘 IO 一次读取出的数据量大小固定，当单个结点数据变大时，将导致磁盘IO次数增加；

• B+ 树，B- 树的进阶，所有的数据都在叶子结点，非叶子结点中只保存索引，不存储数据。因此与B-树相比，B+树中单个结点数据变小，同样大小的磁盘页可以容纳更多的结点元素，树的高度减小，磁盘IO减少。B+树中为每个叶子结点增加一个指针（顺序访问指针），将所有的叶子结点链接起来，这样遍历叶子结点就可以获得全部数据，便于范围查询。因此建议使用 between and 代替 in，如select * from T where k in (1,2,3,4,5)对应5次树的搜索，而select * from T where k between 1 and 5对应1次树的搜索。B+树适用于文件系统与数据索引库，如对于文件系统中的路径a/b/c/d.c，其中非叶子结点a、b与c是索引，d.c是数据，存储在叶子结点。

这里关于 B- 树与 B+ 树的描述过于抽象，下面分别展示两种数据结构的示意图。

B- 树

B+ 树

实现数据库索引时，B+ 树相对于B- 树的优点包括：

• 磁盘读写代价低，单个结点数据小，磁盘IO次数少；
• 查询效率稳定，任何关键字的查找必须走一条从根结点到叶子结点的路，因此所有的关键字查询的路径长度相同，这就是所谓的平衡；
• 便于范围查询与全表扫描，原因是每一个叶子结点有一个指针指向下一个结点，遍历叶子结点就可以实现对整棵树的遍历。

因此，需要根据应用场景的特点选择适用的数据结构来实现索引，目标是实现快与稳定。

数据库底层存储的核心基于数据模型，根据数据模型可以从理论上分析数据库的适用场景。

数据库

不同数据库中使用不同的数据结构实现索引。下面简单介绍几种常见数据库实现索引使用的数据结构。

• Redis，基于哈希表实现，初始化一定数量的哈希桶，根据分配算法将 key 保存到对应的哈希桶，哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。由于哈希桶的数量有限，因此难免出现哈希冲突，redis 中通过将同一个哈希桶中的元素用链表保存。而当哈希冲突越来越多时，哈希冲突链将越来越长，因此引入 rehash 操作通过增加哈希桶数量打散 entry 元素，其中涉及到大量的数据拷贝；

• MySQL，由存储引擎层实现索引，InnoDB 存储引擎中基于 B+ 树实现，因此每个索引都是一棵 B+ 树。每个 InnoDB 表具有一个特殊的索引称为聚簇索引，表中行的物理顺序与索引的逻辑顺序相同。因此在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB 表中在非主键的其他列上建的索引就是二级索引，二级索引的叶子节点中除了存储索引列的值，还存储这一行对应的主键值用于回表。MySQL 8.0 中引入新特性倒序索引，在此之前仅支持正序索引，逆序可能导致全表扫描；

• MongoDB，与 MySQL 的相同点是同样基于 B+ 树实现，同样支持单字段索引（普通索引）与多字段索引（复合索引），主要区别在于支持稀疏索引（Sparse Index）与部分索引（Partial Indexes），可见相比于 MySQL，由于 MongoDB 中每个文档的结构可能不一样，支持的数据类型与索引类型更灵活。稀疏索引是基于字段有没有来建立，而部分索引是基于过滤条件，因此相比于普通索引，稀疏索引于部分索引更加紧促，占用的磁盘空间与内存资源都更少，适用于执行高频的满足特定条件的查询。此外，MongoDB 还支持多键索引，可以给嵌套字段、数组类型的每个元素创建索引，便于数组元素查询；

• ES，不同于 MySQL 中的正排索引，即通过文档查关键词，ES 支持倒排索引，即通过关键词查文档。倒排索引的核心结构是 Term Dictionary 与 Posting List，前者记录所有文档的单词（term），后者记录单词在文档中的位置信息。ES 中通过将所有 term 排序加快 term 的查找效率，类似二分法。但是如果 term 太多，Term Dictionary 也会很大，放内存不现实，于是有了 Term Index，就像字典里的索引页一样，A 开头的有哪些 term，分别在哪页，term index 其实是一棵（Trie） 前缀树，这棵树不会包含所有的 term，它包含的是 term 的一些前缀。通过 term index 可以快速地定位到 Term dictionary 的某个 offset，然后从这个位置再往后顺序查找。

不同类型数据库中索引的具体实现待后续详细分析。

小技巧

list

all 方法是一个生成器函数，其中将符合条件的数据通过 yield 关键字返回给调用方。

    def all(self):
        for item in self.table.all():
            if self.can_index(item):
                yield item

包含 yield 关键字的函数是生成器，而生成器又是特殊的迭代器，迭代器都是可迭代对象，因此生成器可迭代。

生成器需要通过调用__next__/__send__方法驱动执行，那么 all 方法是怎样执行的呢？

ranked 方法中调用 all 方法时通过内置函数 list 遍历传入的可迭代对象将结果保存到列表。

        records = list(self.all())

如下所示，创建 func_gen 生成器函数，直接调用时返回生成器，list 方法调用时返回列表。

>>>def func_gen():
...    for i in range(3):
...        yield i
...        
>>> func_gen
<function func_gen at 0x0000016B591082F0>
>>> func_gen()
<generator object func_gen at 0x0000016B590ED258>
>>> list(func_gen())
[0, 1, 2]

根据官方文档，list 函数是创建列表的一种方式。

class list([iterable])

Lists may be constructed in several ways:

• Using a pair of square brackets to denote the empty list: []
• Using square brackets, separating items with commas: [a], [a, b, c]
• Using a list comprehension: [x for x in iterable]
• Using the type constructor: list() or list(iterable)

如下所示，list 函数使用时：

• 如果参数为空，返回空列表；
• 如果参数是可迭代对象，返回转换成的列表；
• 如果参数本身就是列表，返回原始列表。

>>> list()
[]
>>> list("abc")
['a', 'b', 'c']
>>> list([1, 2, 3])
[1, 2, 3]

因此，实际上 all 方法完全可以用列表推导式替换。

records = [item for item in self.table.all() if self.can_index(item)]

list.sort

ranked 方法中调用 list.sort 方法对数据进行原地排序，没有返回值。

def ranked(self):
    records = list(self.all())
    records.sort(
        key=self.keyfunc,
        reverse=self.reverse,
    )
    return records

list.sort 方法用于列表的原地排序，语法如下所示：

L.sort(key=None, reverse=False) -> None

其中：

• key 用于指定进行比较的元素，只有一个参数，用于指定可迭代对象中的一个元素进行排序；
• reverse 用于指定排序规则，reverse = True 降序 ， reverse = False 升序（默认）。

如下所示，分别指定多字段排序与排序规则。

>>> ss = [(10, "Tom", ), (8, "Jack"), (5, "David"), (10, "Eason")]
>>> ss.sort(key=lambda x: (x[0], x[1]))
>>> ss
[(5, 'David'), (8, 'Jack'), (10, 'Eason'), (10, 'Tom')]

>>> ss = [(10, "Tom", ), (8, "Jack"), (5, "David"), (10, "Eason")]
>>> ss.sort(key=lambda x: x[0], reverse=True)
>>> ss
[(10, 'Tom'), (10, 'Eason'), (8, 'Jack'), (5, 'David')]

可以看到 list.sort 方法是一个接收命名参数 key 的高阶函数 Key Functions。

Key functions in Python are higher-order functions that take a parameter key as a named argument. key receives a function that can be a lambda.

tinyindex 中的排序函数 keyfunc 是一个嵌套函数，内部函数 function 的入参 datum 由 list.sort 传入。

    @property
    def keyfunc(self):
        def function(datum):
            return tuple(datum[k] for k in self.keys)
        return function

其实可以简化为一个普通函数。

    def function(self, datum):
        return tuple(datum[k] for k in self.keys)

结论

tinyindex 中基于有序数组实现索引，具备以下特性：

• 索引针对表级别，有序顺组，基于 list 实现；
• 不仅支持单列索引，还支持多列索引，基于 list.sort 实现；
• 不仅支持顺序索引，还支持逆序索引，基于 list.sort 实现；
• 访问索引时动态创建有序数组，因此数据更新时索引也会更新；
• 由于没有固定的表结构，因此只对指定字段的数据创建索引。

索引是用于优化数据查询操作的数据结构，这些数据结构通过某种方式指向数据，可以快速定位原始数据。

常见的用于实现索引的数据结构与优缺点及适用场景见下表。

数据库底层存储的核心基于数据模型，根据数据模型可以从理论上分析数据库的适用场景。

几种常见数据库实现索引使用的数据结构对比见下表。

待办

• 不同数据库索引的具体实现
• pytest.fixture
• assert

参考教程

• tinydb extensions: tinyindex

• Github: tinyindex

• 《MySQL 是怎样运行的：从根儿上理解 MySQL》第6章 快速查询的秘籍-B+树索引

• MySQL 实战 45 讲：深入浅出索引

• B树、B-树、B+树详解

• 数据库的存储引擎优化是一个扬长避短的过程
• Python 3.11.0 Document: Built-in Types

• Redis核心技术笔记——Redis数据结构

• MongoDB索引详解