我们熟知常用数据库MySQL MongoDB HBase等底层存储都用了各种树结构,如B树LSM树,不过为什么要用这些结构呢?
线性结构在插入查找都会花费大量时间,这点对于数据量大的情况下尤为明显。所以MySQL的引擎几乎没有使用线性索引。MySQL的主流存储引擎都使用B-/B+树索引。
我们先来复习下基础知识:
动态查找树主要有:二叉查找树、平衡二叉树、红黑树、B树、B+树。
前面三种是典型的二叉查找树,查找的时间复杂度是O(log2N)与树的深度有关系,那么降低树的深度也就可以提升查找效率。这时就提出了平衡多路查找树,也就是B树以及B+树。
二叉搜索树(binary search tree)又称为二叉查找树,它或者是一棵空树,要么是具有以下性质的二叉树:
一个可能的二叉树索引如下:
二叉树在保留了二分搜索的前提下,使插入和删除上可以直接修改指针实现,极大提高插入和删除的效率。但是由于二叉树的形状不确定性导致极端查询时间复杂度和平均查询时间复杂度相差很大。例如如果插入数据时本身就是从小到大插入的,那么在构建索引时就会构建出一条极右斜树,他虽然是二叉搜索树,但是这时候对索引的搜索效率等于遍历效率,即O(n),而对于上图情况却最多只需要查找两次。所以就有了平衡二叉树(AVL tree)和红黑树(Red–black tree)
平衡二叉树上所有结点的平衡因子(balance factor)值只能是-1、0、1,保证了查找时的效率问题,但是同样的由于频繁调整树的节点,插入和删除效率下降。而红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。
红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构,能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。
B树是一种平衡多路搜索树,B树与红黑树最大的不同在于,B树的结点可以有多个子女,从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样,一棵含n个结点的B树的高度也为O(lgn),但可能比一棵红黑树的高度小许多,应为它的分支因子比较大。所以,B树可以在O(logn)时间内,实现各种如插入(insert),删除(delete)等动态集合操作。
B树的定义如下:
下图是一个M=4的4阶的B树:
B树的搜索:从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;
B树的特性:
下面是一个B树插入的演示动画,依次插入: 6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
B+树是对B树的一种变形,与B树的差异在于:
如下图一个M=3 的B+树:
B+树的搜索:与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;
B+的特性:
B树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点;所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;
B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;
B+树虽然优点很多,但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。下面是B 树和B+树的区别图:
MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:
这里设表一共有三列,假设我们以Col1为主键,则图8是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,如图:
同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。
InnoDB也使用B+Tree作为索引结构,但具体实现依然是有差异的。
上图是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。
日志结构的合并树(LSM-tree)是一种基于硬盘的数据结构,与B+tree相比,能显著地减少硬盘磁盘臂的开销,并能在较长的时间提供对文件的高速插入(删除)。然而LSM-tree在某些情况下,特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于索引插入比检索更频繁的应用系统。
LSM树核心思想的核心就是放弃部分读能力,换取写入的最大化能力。LSM Tree ,这个概念就是结构化合并树的意思,它的核心思路其实非常简单,就是假定内存足够大,因此不需要每次有数据更新就必须将数据写入到磁盘中,而可以先将最新的数据驻留在内存中,等到积累到足够多之后,再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的,可以通过合并排序的方式快速合并到一起)。
LSM树索引结构上图所示。内存部分导出形成一个有序数据文件的过程称为flush。为了避免flush影响写入性能,会先把当前写入的MemStore设为Snapshot,不再容许新的写入操作写入这个Snapshot的MemStore。另开一个内存空间作为MemStore,让后面的数据写入。一旦Snapshot的MemStore写入完毕,对应内存空间就可以释放。这样,就可以通过两个MemStore来实现稳定的写入性能。
目前常见的主要的三种存储引擎是:哈希、B+树、LSM树:
上面三种引擎中,LSM树存储引擎的代表数据库就是HBase。和B+树不同的是,LSM树的索引对写入请求更友好。因为无论是何种写入请求,LSM树都会将写入操作处理为一次顺序写,而HDFS擅长的正是顺序写(且HDFS不支持随机写),因此基于HDFS实现的HBase采用LSM树作为索引是一种很合适的选择。
LSM树和B+树的差异主要在于读性能和写性能进行权衡。在牺牲的同时寻找其余补救方案:
本文只粗略的讲解了几个树的结构,数据库真正使用的结构其实还有优化