【码农Mark】聊聊C++开发种经常用到的4种层式结构、B+树、时间轮、跳表、LSM-Tree

尾木Whimsy:
有些不明白的我直接问了chatgpt。 跳表和B+树对比，说说各自的优势和应用场景? 答： 跳表（Skip List）： 优势： 简单实现：跳表的数据结构相对较简单，易于理解和实现。 高度平衡：在平均情况下，跳表的高度是O(log n)，使得查询和插入操作的平均时间复杂度为O(log n)。 插入和删除效率高：相对于平衡树，跳表在插入和删除操作上更加高效，因为它不需要像平衡树一样频繁地调整树的结构。 无需平衡维护：跳表不需要像B+树一样频繁地进行平衡维护操作。 应用场景： 内存数据库：跳表在内存数据库中具有广泛的应用，因为它可以高效地支持范围查询和插入操作。 游戏开发：跳表可以用于实现游戏中的排行榜功能，快速查找和更新玩家排名。 高性能的索引数据结构：跳表可以用作高性能的索引数据结构，用于加速搜索和检索操作。 B+树： 优势： 磁盘存储优化：B+树是一种在磁盘上存储和检索数据的优秀选择，因为它具有良好的局部性，适合于大规模数据存储和查询。 范围查询高效：B+树可以非常高效地支持范围查询，因为相邻的节点在磁盘上通常也是相邻的，这减少了磁盘I/O操作。 多路平衡：B+树是一种多路平衡树，适用于高度动态的数据结构，能够在插入和删除操作时自动维护平衡。 应用场景： 数据库系统：B+树广泛用于关系型数据库中的索引结构，以支持高效的数据检索操作。 文件系统：B+树可以用于构建文件系统中的目录和索引结构，支持文件的快速查找和管理。 键值存储引擎：B+树常用于实现键值存储引擎，如Redis和LevelDB，用于高效存储和检索键值对数据。 总之，跳表适用于内存中的数据存储和检索，尤其在需要频繁插入和删除操作以及不需要频繁平衡维护的场景下效果很好。而B+树适用于磁盘存储、范围查询和需要维护平衡的场景，如数据库系统和文件系统。选择合适的数据结构应根据具体应用的需求和性能要求来决定。

【回复】回复 @尾木Whimsy : 问：跳表不需要平衡维护，所以长时间存储可能导致不平衡吗？ 答：是的，跳表不需要像平衡树（如AVL树或红黑树）那样频繁进行平衡维护，但长时间的插入和删除操作可能会导致跳表的不平衡。虽然跳表的平均高度是O(log n)，但这仅是期望的情况。 在实际应用中，如果大量的插入或删除操作不是随机分布的，而是在某个特定区域集中进行，那么跳表可能会变得不平衡，高度可能会远远超过期望的O(log n)。这会导致查询操作的性能下降，因为查询的速度取决于跳表的高度。
【回复】考虑到大数定律，插入的数据越多，层高越趋于期望。个人理解是：层高的期望只受节点的多少影响，不受节点插入先后顺序和数据（节点）的分布影响。即便数据不是随机分布对层高也无影响
码农Mark:
https://www.bilibili.com/video/BV1394y1s7gh/?vd_source=755959927aac9d0409d9441f79a875e5

breaking-wave:
写过简单的lsm，但是当时没实现immutable跳表，学习了