【技术课堂】聊一聊数据库中的经典算法和数据结构

存储引擎是数据库的核心部分。我们在设计数据库时,需要考虑如何组织数据来提高写入的吞吐、降低查询的延迟,而这些都与存储引擎息息相关。存储引擎数不胜数,但核心的数据结构却万变不离其宗。用于存储引擎的主流数据结构有哪些呢?

B 树(B+ 树)

B 树(B+树)是为磁盘等外存储设备设计的一种平衡查找树。它是一种经典的数据结构,目前主流数据库产品大都支持 B 树。B 树结构可以让系统高效地找到数据所在的磁盘块。如图所示,节点[13,16,19]拥有的子节点数目最多,因此,该 B 树为一个 4 阶 B 树。

【技术课堂】聊一聊数据库中的经典算法和数据结构 - TDengine Database 时序数据库

B 树(B+ 树)在查询过程中,相比平衡二叉树,降低了树高,从而能够减少 IO 次数,因此更适用于硬盘。但写入过程中却可能导致节点的分裂,产生大量随机。IO,导致写入性能的降低。

像 SQLite , MySQL,  PostgreSQL 等数据库都使用了B/B+ 树。

LSM 树

LSM 树(Log-Structured-Merge Tree)并不像 B+ 树、红黑树一样是一个严格的树状数据结构,它其实是一种存储结构,目前 HBase, LevelDB, RocksDB 这些 NoSQL 数据库中,新一代关系型数据库 TiDB, CockroachDB 也建立在基于 LSM 树的 KV 存储上。下图展示了 LSM 树的核心思想。

【技术课堂】聊一聊数据库中的经典算法和数据结构 - TDengine Database 时序数据库

LSM 树充分利用了硬盘顺序 IO 速度远超随机 IO 的特点,避免了写入过程中节点分裂带来的大量 IO,从而能够发挥更强大的写入性能。但与此同时,LSM 树在查询过程中却可能需要遍历多级文件,导致查询性能的下降。

基于 B 树(B+ 树)或 LSM 树的通用存储引擎,久经考验能够良好地支持关系型或非关系型的数据库。但时序数据库如 TDengine、InfluxDB 等都选择了针对时序数据的特点,量身定做存储引擎,从而在性能上远超基于通用存储引擎建立的数据库。InfluxDB 探索了基于 LevelDB、BoltDB、RocksDB 等等方案,但最终选择了构建自己的存储引擎。而 TDengine 从一开始就发现通用存储引擎难以充分发挥时序数据的典型特征,为了将性能发挥到极致,自研了用于时序数据的存储引擎。

那么,时序数据的典型特征是什么呢?对于时序数据来说,为什么通用的 KV 存储引擎不够优秀?如何针对时序数据,打造专用的存储引擎,从而尽可能地提高读写吞吐、降低延迟呢?

2021 年 12 月 16 日(周四)20:00-21:00,我们邀请到了 TDengine Database 工程师刘继聪,和大家聊一聊数据库的经典算法和数据结构。

刘继聪,毕业于复旦大学,计算机科学与技术专业,曾就职于阿里云,现涛思数据存储引擎研发工程师。

他分享的主要内容:

  1. 时序数据的典型特征
  2. 经典数据结构 B Tree(B+ Tree)
  3. 经典数据结构 LSM Tree
  4. 如何充分利用时序数据的特点,打造专用存储引擎

欢迎大家扫描下方二维码,关注 TDengine Database 的视频号,观看每周的微课堂以及直播活动。

【技术课堂】聊一聊数据库中的经典算法和数据结构 - TDengine Database 时序数据库