第2章 基础数据结构与算法

著名的计算机科学家N.Wirth说过：程序=算法+数据结构。对于HBase这样的一个分布式数据库来说，它的代码规模已经非常庞大，如果加上测试代码以及序列化工具（Protobuf/Thrift）生成的代码，HBase项目（2.0分支）代码行数已经突破150万。但是，即使这样庞大的项目也是由一个个算法和数据结构组成。

本章将会介绍HBase用到的一些核心算法和数据结构。这里，我们假设读者已经具备了“数据结构”课程相关的基础知识，例如链表、栈、队列、平衡二叉树、堆等。

HBase的一个列簇（Column Family）本质上就是一棵LSM树（Log-Structured Merge-Tree）。LSM树分为内存部分和磁盘部分。内存部分是一个维护有序数据集合的数据结构。一般来讲，内存数据结构可以选择平衡二叉树、红黑树、跳跃表（SkipList）等维护有序集的数据结构，这里由于考虑并发性能，HBase选择了表现更优秀的跳跃表。磁盘部分是由一个个独立的文件组成，每一个文件又是由一个个数据块组成。对于数据存储在磁盘上的数据库系统来说，磁盘寻道以及数据读取都是非常耗时的操作（简称IO耗时）。因此，为了避免不必要的IO耗时，可以在磁盘中存储一些额外的二进制数据，这些数据用来判断对于给定的key是否有可能存储在这个数据块中，这个数据结构称为布隆过滤器（Bloom Filter）。

本章将介绍HBase的核心数据结构，主要包括跳跃表、LSM树和布隆过滤器。同时，为了使读者加深印象，我们设计了一个轻量级KV存储引擎MiniBase，并提供了一些相关的编程练习。