在讲解HBase的LSM合并树之前，我们需要来了解一些常用的数据结构知识。
跳表
链表
上图是一个有序链表，我们要检索一个数据就挨个遍历。如果想要再提升查询效率，可以变种为以下结构：
跳表
现在，我们要查询11，可以跳着来查询，从而加快查询速度。
常见树结构二叉搜索树（Binary Search Tree）什么是二叉搜索树？二叉搜索树也叫二叉查找树。它是一种比较特殊的二叉树。
二叉树
树的高度、深度、层数- 深度
节点的深度是根节点到这个节点所经历的边的个数，深度是从上往下数的
- 高度
节点的高度是该节点到叶子节点的最长路径（边数），高度是从下往上数的
- 层数
根节点为第一层，往下依次递增
上图：
- 节点12的深度为0，高度为4，在第1层
- 节点15的深度为2，高度为2，在第3层
树中的每个节点，它的左子树中所有关键字值小于该节点关键字值，右子树中所有关键字值大于该节点关键字值
二叉搜索树的查询方式- 首先和根节点进行比较，如果等于根节点，则返回
- 如果小于根节点，则在根节点的左子树进行查找
- 如果大于根节点，则在根节点的右子树进行查找
因为二叉搜索树是一种二叉树，每个节点只能有两个子节点，但有较多节点时，整棵树的高度会比较大，树的高度越大，搜索的性能开销也就越大
平衡二叉树（Balance Binary Tree）简介- 平衡二叉树也称为AVL数
- 它是一颗空数，或者它的任意节点左右两个子树的高度差绝对值不超过1
- 平衡二叉树很好地解决了二叉查找树退化成链表的问题
