点击查看第一章
点击查看第三章
第2章

基础数据结构与算法

著名的计算机科学家N.Wirth说过：程序=算法+数据结构。对于H 这样的一个分布式数据库来说，它的代码规模已经非常庞大，如果加上测试代码以及序列化工具（Protobuf/Thrift）生成的代码，H 项目（2.0分支）代码行数已经突破150万。但是，即使这样庞大的项目也是由一个个算法和数据结构组成。
本章将会介绍H 用到的一些核心算法和数据结构。这里，我们假设读者已经具备了“数据结构”课程相关的基础知识，例如链表、栈、队列、平衡二叉树、堆等。
H 的一个列簇（Column Family）本质上就是一棵LSM树（Log-Structured Merge-Tree）。LSM树分为内存部分和磁盘部分。内存部分是一个维护有序数据集合的数据结构。一般来讲，内存数据结构