在大规模数据存储中，实现索引查询也是一个重难点，由于树节点存储的元素数量有限，因此就会导致在应用二叉搜索树结构时，会因为树深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。那不同的索引区别在哪里？时序数据库（TimeSeriesDatabase）又应该如何选择索引方式实现科学的数据结构？本文将以TDengine为例为大家展开分析。
B树、B+树、LSM树B树即平衡多路查找树，也称为B-树。通常我们描述一棵B树时需要指定它的阶数，阶数表示一个节点最多有多少个孩子节点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。B树是一种自平衡树状数据结构，能对存储的数据进行O(logn)的时间复杂度进行查找、插入和删除，一般较多用在存储系统上，比如数据库或文件系统。
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存储和查询引擎。在TDengine2.0中，TSDB存储了一个Vnode中表的元数据以及时序数据（采集信息），后者以行和列两种结构存储（2.0开始引入行存储），时序数据在内存中以SkipList方式进行索引，在硬盘中以BlockRangeINdex（BRIN）方式进行索引。
TSDB启动时会事先分配一个BUFFERPOOL作为写入缓冲（默认16MB*6=96MB），缓冲区块大小和个数可配，区块个数可修改。元数据和时序数据从缓冲块申请写入空间，写入引擎向BUFFERPOOL申请缓冲区块，写满的缓冲区块占总缓冲区块的三分之一时触发落盘操作。落盘时，缓冲区块中的数据写入到META等文件中，落盘结束后缓冲区块归还给BUFFERPOOL，形成循环机制。查询时，对MEM、IMEM以及数据文件中的数据进行合并查询。如下图所示：
这种设计的优势在于：
对于单表按照时间段的查询效率很高
内存行存储充分利用内存，缓存更多数据
文件中列存储充分发挥压缩算法优势
避免LSM过多的文件合并
标签数据与时序数据分离存储
但也存在一些不足之处。在元数据存储这块，此前的1.0和2.0采取的都是比较简单的存储机制，即全内存存储，数据在内存中以hash表的方式存储，并辅以跳表索引，在hash表中有一个BackupStorageEngine，它可以保证数据的持久化。该方式的优点是全内存、效率高，但缺点也很明显，当启动时，这部分数据就会全部加载到内存之中，不仅内存占用无法精准控制，还会导致开机启动时间长。
因此，为了解决这些问题，我们在TDengine3.0中研发了TDB（一个B+树格式的的存储引擎），来存储元数据及元数据索引。TDB的B+树存储适合元数据读多写少的场景，能够支持百亿时间线的存储，避免了元数据全内存存储以及长时间的加载，同时解决了在有限内存下，表数量膨胀的问题。对于TDB是如何实现的，大家如果感兴趣，可以去GitHub（