共计 3200 个字符，预计需要花费 8 分钟才能阅读完成。
在大规模数据存储中，实现索引查问也是一个重难点，因为树节点存储的元素数量无限，因而就会导致在利用二叉搜寻树结构时，会因为树深度过大而造成磁盘 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 才体现出强劲的存储性能和查问性能。如果你也面临着时序数据处理难题或想要和咱们的外围研发人员进行交换和沟通，欢送增加小 T（tdengine），和一众气味相投的开发者共同进步。
