在大规模数据存储中，实现索引查询也是一个重难点，由于树节点存储的元素数量有限，因此就会导致在应用二叉搜索树结构时，会因为树深度过大而造成磁盘 I/O 读写过于频繁，进而导致查询效率低下。那不同的索引区别在哪里？时序数据库（Time Series Database）又应该如何选择索引方式实现科学的数据结构？本文将以 TDengine 为例为大家展开分析。
B树、B+树、LSM树
B树即平衡多路查找树，也称为B-树。通常我们描述一棵B树时需要指定它的阶数，阶数表示一个节点最多有多少个孩子节点，一般用字母 m 表示阶数。当 m 取 2 时，就是我们常见的二叉搜索树。B树是一种自平衡树状数据结构，能对存储的数据进行 O(log n) 的时间复杂度进行查找、插入和删除，一般较多用在存储系统上，比如数据库或文件系统。
B+树是B树的一种变体，也属于平衡多路查找树，大体结构与B树相同，包含根节点、内部节点和叶子节点，多用于数据库和操作系统的文件系统中，由于B+树内部节点不保存数据，所以能在内存中存放更多索引，增加缓存命中率。另外因为叶子节点相连遍历操作很方便，而且数据也具有顺序性，便于区间查找。
B+树每个非叶子节点存放的元素只用于索引作用，所有数据保存在叶子节点中。一个 m 阶的B+树规定了：
- 有 k 个子树的中间节点包含有 k 个元素（B树中是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点；
- 所有的叶子节点中包含了全部元素的信息，及指向包含这些元素记录的指针，且叶子节点本身以关键字的大小自小而大的顺序链接；
- 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
因为非叶子节点中存放的元素不存放数据，所以每一层可以容纳更多的元素，即磁盘中的每一页可以存放更多元素，这样在查找时，磁盘 IO 的次数也会减少。另外，B+树的查找要更稳定一些，因为其所有的数据都在叶子节点，而每个叶子节点通过指针构成了一种链表结构，因此遍历数据也会简单很多。
B+树的插入和删除与B树类似，它们的区别主要有以下几点：
- B+树内节点不存储数据，所有数据存储在叶节点(非叶子节点并不存储真正的 data)，也因此导致查询时间复杂度固定为 log（n）。而B树可以在内部节点同时存储键和值，因此，我们把频繁访问的数据放在靠近根节点的地方将会大大提高热点数据的查询效率，这种特性使得B树在特定数据重复多次查询的场景中更加高效。B树查询时间复杂度不固定，与 key 在树中的位置有关，最好的情况下时间复杂度为 O(1)。
- B+树的叶子节点有一条链相连，而B树的叶子节点各自独立。B+树叶节点两两相连可大大增加区间访问性，可使用在一定范围内查询等，而B树每个节点 key 和 data 在一起，则无法区间查找。
- B+树更适合外部存储，由于内节点无 data 域，每个节点能索引的范围更大更精确。B树节点内部每个 key 都带着 data 域，B+树节点只存储 key 的副本，真实的 key 和 data 域都在叶子节点存储，而磁盘是分 block 的，一次磁盘 IO 会读取若干个 block，具体和操作系统有关，那么由于磁盘 IO 数据大小是固定的，在一次 IO 中，单个元素越小量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B树，从这点来看B+树相对B树磁盘 IO 次数少。
B树最大的好处在于它对数据持续高涨读性能的处理上，即使数据量级增大，它的读也没有放大，其奥秘在于对数据进行终极持久存储时，B树是以有规律的数据结构保存在硬盘上的。这样随着数据越来越大，它依然保持着有序有规律的特性，即便面对成千上万的读操作，都可以遵循条件运行，减少或避免读放大的行为。
B树/B+树在数据库存储中应用非常广泛，它能对数据进行有效地查找，避免了读放大。此外，B树和LSM经常一起使用。数据库底层可以分为B树机制、LSM机制，两种机制各有各的优点和缺点。与B树机制截然相反，LSM机制则是减少避免了写放大。LSM机制充分利用了内存，在内存里面开辟了一个空间，写数据优先往内存里放，写进去直接返回用户成功，而不是像B树那样写一个，要找出谁更大谁更小，只要内存足够，就直接往内存里面填就好，当内存达到一定的阈值后就会将内存中的数据以批量、顺序的方式一次写入硬盘上，内存则重置清零再服务新的写要求。
传统数据库 MySQL、Oracle 使用的都是B树机制，而 TiDB、OceanBase 一类的数据库使用的则是优化后的 LSM 机制。TDengine 使用的是B树 + LSM机制的方式，B树存储的是元数据（主要是时间戳+指标数据），LSM机制存储的是具体的数据，元数据以有序表结构方式进行存储，而具体数据则是追加的方式写入，这样既避免了读放大又避免了写放大。
时序数据库如何构建索引？
以 TDengine 为例，针对时序数据的特点，我们专门研发了 TSDB 存储和查询引擎。在 TDengine 2.0 中，TSDB 存储了一个 Vnode 中表的元数据以及时序数据（采集信息），后者以行和列两种结构存储（2.0开始引入行存储），时序数据在内存中以 SkipList 方式进行索引，在硬盘中以 Block Range INdex（BRIN）方式进行索引。
TSDB 启动时会事先分配一个BUFFER POOL 作为写入缓冲（默认16MB*6=96MB），缓冲区块大小和个数可配，区块个数可修改。元数据和时序数据从缓冲块申请写入空间，写入引擎向 BUFFER POOL 申请缓冲区块，写满的缓冲区块占总缓冲区块的三分之一时触发落盘操作。落盘时，缓冲区块中的数据写入到 META 等文件中，落盘结束后缓冲区块归还给 BUFFER POOL，形成循环机制。查询时，对 MEM、IMEM 以及数据文件中的数据进行合并查询。如下图所示：
这种设计的优势在于：
- 对于单表按照时间段的查询效率很高
- 内存行存储充分利用内存，缓存更多数据
- 文件中列存储充分发挥压缩算法优势
- 避免 LSM 过多的文件合并
- 标签数据与时序数据分离存储
但也存在一些不足之处。在元数据存储这块，此前的 1.0 和 2.0 采取的都是比较简单的存储机制，即全内存存储，数据在内存中以 hash 表的方式存储，并辅以跳表索引，在 hash 表中有一个 Backup Storage Engine，它可以保证数据的持久化。该方式的优点是全内存、效率高，但缺点也很明显，当启动时，这部分数据就会全部加载到内存之中，不仅内存占用无法精准控制，还会导致开机启动时间长。
因此，为了解决这些问题，我们在 TDengine 3.0 中研发了 TDB（一个 B+ 树格式的的存储引擎），来存储元数据及元数据索引。TDB 的 B+ 树存储适合元数据读多写少的场景，能够支持百亿时间线的存储，避免了元数据全内存存储以及长时间的加载，同时解决了在有限内存下，表数量膨胀的问题。对于 TDB 是如何实现的，大家如果感兴趣，可以去 GitHub 上看一下源代码。
TDB 的优点是内存可以精确控制，开机启动速度快，在有限内存下也可以存储海量的元数据，此外如果 TDB 外加 Cache 辅助的话，在一定程度上可以提供接近全内存 hash 表的查询速度。事实上，关于 TDengine 3.0 存储引擎的更新可以分为三大块，首先是 TQ，基于 WAL 的消息队列；其次是 META，基于 TDB 的元数据存储引擎；第三是 TSDB，用来存储时序数据的类 LSM 存储引擎（TSDB SE）。关于 TQ 和 TSDB 的具体更新感兴趣的小伙伴可以进入《支持消息队列和流式计算背后，TDengine 3.0 存储引擎的优化与升级》一文查看。
结语
在对时序数据特点进行挖掘和总结的前提下，TDengine 设计了存储模型和查询模型，摸索到了最适合进行时序数据处理的索引结构，正因为这些创新设计，TDengine 才表现出强劲的存储性能和查询性能。如果你也面临着时序数据处理难题或想要和我们的核心研发人员进行交流和沟通，欢迎联系我们，和一众志同道合的开发者共同进步。
