图文详见我的微信公众号<<大数据架构之道与术>> URL如下：

数据库数据结构索引&B树&B+树&LSM树解密

https://mp.weixin.qq.com/s?__biz=Mzg4MTY3MzA0NQ==&mid=2247484073&idx=1&sn=f3bb5f74c301b1d80c70d30cbd86b3ec&chksm=cf631493f8149d85085378d264ef916197e4f13f352fa434b2420ac16f0cb620f8cc597d2560

 我的原创。

 

----------------------------------------------------------------------------------------------------------------

 

数据库数据结构-索引

 

对于一个数据库的性能来说，其数据的组织方式至关重要。从数据库的文件组织方式聊起。众所周知，数据库的数据大多存储在磁盘上，而磁盘的访问相对内存的访问来说是一项很耗时的操作。因此，提高数据库数据的查找速度的关键点之一便是尽量减少磁盘的访问次数。

 

 

 

为了加速数据库数据的访问，大多传统的关系型数据库都会使用特殊的数据结构来帮助查找数据，这种数据结构叫作索引(Index)。

 

对于传统的关系型数据库，考虑到经常需要范围查找某一批数据，因此其索引一般不使用Hash算法，而使用树(Tree)结构。然而，树结构的种类很多，却不一定都适合用于做数据库索引。

 

索引对树结构的选择

 

1.二叉查找树与平衡二叉树

 

最常见的树结构是二叉查找树(Binary Search Tree),它就是一颗二叉有序树：保证左子树上所有节点的值都小于根节点的值，而右子树上所有

 

节点的值都大于根节点的值。其优点在于实现简单，并且树在平衡的状态下查找效率能达到O(log2N);缺点是在极端非平衡情况下查找效率会退化到O(N),

 

因此很难保证索引的效率。

 

针对上述二叉查找树的缺点，人们很自然就想到是否能用平衡二叉树(Balanced Binary Tree)来解决这个问题。但是平衡二叉树依然有个比较大的问题：它的

 

树高为log2N——对于索引树来说，树的高度越高，意味着查找所要花费的访问次数就越多，查询效率越低。

 

况且，主存从磁盘读数据一般以页为单位，因此每次访问磁盘都会读取多个扇区的数据(比如4KB大小的数据)，远大于单个二叉树节点的值(字节级别)，这也是

 

造成二叉树相对索引树效率地下的原因。正因如此，人们就想到了通过增加每个树节点的度来提高访问效率，而B+树(B+-tree)便受到了更多的关注。

 

2.B+树

 

在传统关系型数据库里，B+树(B+-tree)及其衍生树是被用的比较多的索引树。

B+树的主要特点如下:

 

(1)每个树节点只放键值，不存放数值，而由叶子节点存放数值。这样会使树节点的度比较大，而树的高度就比较低，从而有利于提高查询效率。

 

(2)叶子节点存放数值，并按照值大小顺序排序，且带指向相邻节点的指针，以便高效地进行区间数据查询；并且所有叶子节点与根节点的距离相同，

 

因此任何查询的效率都很相似。    

 

(3)与二叉树不同，B+树的数据更新操作不从根节点开始，而从叶子节点开始，并且在更新过程中树能以比较小的代价实现自平衡。

 

正是由于B+树的上述优点，它成了传统关系型数据库的宠儿。

 

当然，它页并非无懈可击，它的主要缺点在于随着数据插入的不断发生，叶子节点会慢慢分裂——这可能会导致逻辑上原本连续的数据实际上存放在不同的物理磁盘块位置上，在做范围查询的时候会导致较高的磁盘IO，以致严重影响到性能。

 

3.日志结构合并树LSM-tree(Log-Structured Merge-Tree)

 

众所周知，数据库的数据大多存储在磁盘上，而无论是传统的机械硬盘(HDD Hard Disk Drive)还是固态硬盘(SSD Solid State Drive,SSD)，对磁盘数据的顺序读写速度都远高于随机读写。

 

然而，基于B+树的索引结构是违背上述磁盘基本特点的——它会需要较多的磁盘随机读写，于是1992年名为日志结构(Log-Structured)的新型索引结构方法便应运而生。

 

日志结构方法的主要思想是将磁盘看做一个大的日志，每次都将新数据和索引结构添加到日志的最末端，以实现对磁盘的顺序操作，从而提高索引性能。

 

不过日志结构方法也有明显的缺点，随机读取数据时效率很低。

 

1996年，一篇名为The log-structured merge-tree(LSM-tree)的论文创造性地提出了日志结构合并树(Log-Structured Merge-Tree)的概念，该方法既吸收了日志结构方法的优点，又通过将数据文件预排序克服了日志结构方法随机读性能较差的问题。

 

直到10年后的2006年谷歌的Bigtable论文使用LSM-Tree技术开始流行。随后2007年的HBase与2008年的Cassandra在LSM-Tree思想基础上诞生，极大推广了LSM-tree技术。

 

LSM-tree的核心思想是同时使用两部分类树的数据结构来存储数据，并同时提供查询。其中一部分数据结构存在内存缓存(memtable)负责插入更新和读请求，并在内存中进行排序；另一部分写在磁盘(sstable),负责读操作，有序且不能更改。

 

使用日志文件做数据恢复保障，所有操作记录先写Log，再写memtable，最后冲写到sstable

 

定期合并小sstable以减少sstable数量，对每个sstable使用布隆过滤器，以加速数据存在与否的判定，从而减少数据的总查询时间。

 

LSM-tree 显然比较适合那些数据插入操作远多于数据更新删除操作与读操作的场景。同时Druid在一开始就是为时序数据场景设计的，而该场景正好符合LSM-tree的优势特点，因此DRUID架构便顺理成章地吸收了LSM-tree的思想。DRUID采用了类LSM-tree架构。

 

Druid不提供日志及实行WAL原则 实时节点堆结构缓存区(memtable) 内存非堆区 数据块Segment Split。实时节点会周期性地将磁盘上同一个时间段内生成的所有的数据块合并为一个大的数据块(Segment)，这个过程在实时节点中叫作Segment Merge操作也相当于LSM-tree架构中的数据合并操作(Compaction)。合并好的Segment会被传到DeepStorage中。

 

Druid 高速写入 没有WAL 不适应于数据更新场景，降低了数据完整性的保障。性能方面要更好一些。

 

------------------------------------------------------------------------

 

索引

 

提高数据库查找速度的关键之一是减少磁盘的访问次数，并采用树形结构做索引

 

 

 

二叉查找树和平衡二叉树

 

二叉查找树在极端非平衡情况下查询效率会退化到O(N),因此尝试采用平衡二叉树；但是平衡二叉树的树高为:

 

log2 N

 

树高越高，查询次数越多越慢。同时，每次访问磁盘会读取多个扇区的数据，远大于单个树节点的值，造成浪费

 

B+树

 

传统关系型数据库的常用结构。

 

每个树节点只放键值，不放数值，叶子节点存放数值，使得树高度较低

 

叶子节点按值大小顺序排序，带指向相邻节点的指针，方便区间数据查询

 

从叶子节点开始更新，以较小的代价实现自平衡

 

缺点是随着数据插入，叶子节点会分裂，导致连续数据被存放在不同的物理磁盘块上，导致较大的IO开销

 

日志结构合并树（LSM）

 

日志结构的所有方式的将磁盘看做一个大的日志，每次都将新数据和索引结构添加到最末端；LSM通过将数据文件预排序解决了日志结构随机读性能差的问题。

 

使用两颗树来存储数据，其中一部分数据结构存在内存负责插入更新和读请求，并在内存中进行排序；另一部分写在磁盘,负责读操作，有序且不能更改

 

使用日志文件做数据恢复保障，所有操作记录先写Log，再写memtable，最后冲写到sstable

 

定期合并小sstable以减少sstable数量，对每个sstable使用布隆过滤器，以加速数据存在与否的判定

 

=================================================================================

 

树的层数和度的概念

 

层数：根节点为第一层，往下一次递增。

树中节点的最大层数称之为树的深度或者高度，所以在基数为1时树的深度=树的高度=最大层数

但是节点的深度和高度并没有必然的关系

 

节点的度：节点拥有的子树的个数，度为0的节点称之为叶子节点

树的度：是树内所有节点度的最大值

树的深度：树内所有节点深度的最大值，也就是所有叶子节点深度的最大值，也就是树的层数

树的高度：树内所有节点高度的最大值，也就是根节点的高度，也就是树的层数

 

节点的度：结点拥有的子树数目称为结点的度，叶子结点 就是度为0的结点

树的度：树内各结点的度的最大值

 

树的深度与高度

节点 ni 的深度：从根节点到 ni 的的唯一路径长。即，节点 ni 所在的层次（根节点为0层），树的深度 = 树中节点的最大层次。

节点 ni 的高度：从 ni 到一片树叶的最长路径长。即，叶子节点的高度为0，树的高度 = 根的高度。

 

树的深度 = 树的高度

高度为h的二叉树至少2^h个节点，至多有2^（h+1）-1 个节点。

含有n≥1 个节点的二叉树的高度范围：[ | log2 n」,n-1]

 

0_1 完全二叉树

只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置。

有 n 个节点的完全二叉树的高度（深度）为 | log2 n」

完全二叉树第 n 层上至多 2^(n+1)个节点

完全二叉树第 n 层上节点编号： 2^n - 2^(n+1)-1

 

0_2 满二叉树

是一颗完全二叉树；除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层。

第 n 层有 2^(n+1)-1 个节点

深度为k，且有 2^(k+1)－1个节点。

 

1.二叉排序树（二叉查找树）

左子树上的值都小于根结点的值，右子树上的值都大于根结点得值，左右子树都是二叉排序树。

 

2.平衡二叉树（ALV）

是一颗二叉排序树；左子树和右子树的高度差值不超过1，左右子树都为平衡二叉树。

插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)

插入操作：在平衡二叉树中插入结点与二叉查找树最大的不同在于要随时保证插入后整棵二叉树是平衡的。那么调整不平衡树的基本方法就是： 旋转，基本思路都是转换到左旋和右旋。

 

3.红黑树：

与AVL类似，平衡二叉B树，并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

 

平衡树-B树 

B树就是B-树，"-"是个连字符号，不是减号。

 

B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。（相对于二叉，B树每个内结点有多个分支，即多叉）

 

B-树是一种平衡的多路查找(又称排序)树，在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance)

 

B树的优势是当你要查找的值恰好处在一个非叶子节点时，查找到该节点就会成功并结束查询，而B+树由于非叶节点只是索引部分，这些节点中只含有其子树中的最大(或最小)关键字，当非终端节点上的关键字等于给点值时，查找并不终止，而是继续向下直到叶子节点。因此在B+树中，无论查找成功与否，都是走了一条从根到叶子节点的路径。

 

B+树有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了。

 

B+树支持range-query(区间查询)非常方便，而B树不支持。这是数据库选用B+树的最主要原因。

 

有很多基于频率的搜索是选用B树，越频繁query的结点越往根上走，前提是需要对query做统计，而且要对key做一些变化。 另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。 mysql底层存储是用B+树实现的，因为内存中B+树是没有优势的，但是一到磁盘，B+树的威力就出来了。

 

B+树

在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能

 

根节点和枝节点很简单，分别记录每个叶子节点的最小值，并用一个指针指向叶子节点。

 

叶子节点里每个键值都指向真正的数据块（如Oracle里的RowID），每个叶子节点都有前指针和后指针，这是为了做范围查询时，叶子节点间可以直接跳转，从而避免再去回溯至枝和跟节点。

 

B+树最大的性能问题是会产生大量的随机IO，随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，但做范围查询时，会产生大量读随机IO。

 

对于大量的随机写也一样，举一个插入key跨度很大的例子，如7->1000->3->2000 ... 新插入的数据存储在磁盘上相隔很远，会产生大量的随机写IO。

 

从上面可以看出，低下的磁盘寻道速度严重影响性能（近些年来，磁盘寻道速度的发展几乎处于停滞的状态）。

 

LSM-Tree

 

LSM树是HBase里非常有创意的一种数据结构，它和传统的B+树不太一样，下面先说说B+树。

 

为了克服B+树的弱点，HBase引入了LSM树的概念，即Log-Structured Merge-Trees。

 

为了更好的说明LSM树的原理，下面举个比较极端的例子：

 

现在假设有1000个节点的随机key，对于磁盘来说，肯定是把这1000个节点顺序写入磁盘最快，但是这样一来，读就悲剧了，因为key在磁盘中完全无序，每次读取都要全扫描；

 

那么，为了让读性能尽量高，数据在磁盘中必须得有序，这就是B+树的原理，但是写就悲剧了，因为会产生大量的随机IO，磁盘寻道速度跟不上。

 

LSM树本质上就是在读写之间取得平衡，和B+树相比，它牺牲了部分读性能，用来大幅提高写性能。

 

它的原理是把一颗大树拆分成N棵小树， 它首先写入到内存中（内存没有寻道速度的问题，随机写的性能得到大幅提升），在内存中构建一颗有序小树，随着小树越来越大，内存的小树会flush到磁盘上。当读时，由于不知道数据在哪棵小树上，因此必须遍历所有的小树，但在每颗小树内部数据是有序的。

 

以上就是LSM树最本质的原理，有了原理，再看具体的技术就很简单了:

 

1）首先说说为什么要有WAL（Write Ahead Log），很简单，因为数据是先写到内存中，如果断电，内存中的数据会丢失，因此为了保护内存中的数据，需要在磁盘上先记录logfile，当内存中的数据flush到磁盘上时，就可以抛弃相应的Logfile。

2）什么是memstore, storefile？很简单，上面说过，LSM树就是一堆小树，在内存中的小树即memstore，每次flush，内存中的memstore变成磁盘上一个新的storefile。

3）为什么会有compact？很简单，随着小树越来越多，读的性能会越来越差，因此需要在适当的时候，对磁盘中的小树进行merge，多棵小树变成一颗大树。

 

 

为什么说B+树比B树更适合数据库索引？

1、 B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2、B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3、由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

 

 

B+树在MyISAM索引实现

叶节点的data域存放的是数据记录的地址

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

 

B+树在InnoDB索引实现

第一个重大区别是InnoDB的数据文件本身就是索引文件。

从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。

这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

从示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

 

所以应该注意的地方

为什么不建议使用过长的字段作为主键？

因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。

在InnoDB中不要用非单调的字段作为主键。

因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

=================================================================================

另外一个角度分析树

 

一、二叉查找树与平衡二叉树

最常见的树结构是二叉查找树(Binary Search Tree),它就是一颗二叉有序树：保证左子树上所有节点的值都小于根节点的值，而右子树上所有

节点的值都大于根节点的值。其优点在于实现简单，并且树在平衡的状态下查找效率能达到O(log2N);缺点是在极端非平衡情况下查找效率会退化到O(N),

因此很难保证索引的效率。

针对上述二叉查找树的缺点，人们很自然就想到是否能用平衡二叉树(Balanced Binary Tree)来解决这个问题。但是平衡二叉树依然有个比较大的问题：它的

树高为log2N——对于索引树来说，树的高度越高，意味着查找所要花费的访问次数就越多，查询效率越低。

况且，主存从磁盘读数据一般以页为单位，因此每次访问磁盘都会读取多个扇区的数据(比如4KB大小的数据)，远大于单个二叉树节点的值(字节级别)，这也是

造成二叉树相对索引树效率地下的原因。正因如此，人们就想到了通过增加每个树节点的度来提高访问效率，而B+树(B+-tree)便受到了更多的关注。

 

二、B+树

在传统关系型数据库里，B+树(B+-tree)及其衍生树是被用的比较多的索引树。

B+树的主要特点如下:

(1)每个树节点只放键值，不存放数值，而由叶子节点存放数值。这样会使树节点的度比较大，而树的高度就比较低，从而有利于提高查询效率。

(2)叶子节点存放数值，并按照值大小顺序排序，且带指向相邻节点的指针，以便高效地进行区间数据查询；并且所有叶子节点与根节点的距离相同，

因此任何查询的效率都很相似。    

(3)与二叉树不同，B+树的数据更新操作不从根节点开始，而从叶子节点开始，并且在更新过程中树能以比较小的代价实现自平衡。

 

正是由于B+树的上述优点，它成了传统关系型数据库的宠儿。

当然，它页并非无懈可击，它的主要缺点在于随着数据插入的不断发生，叶子节点会慢慢分裂——这可能会导致逻辑上原本连续的数据实际上存放在不同的物理磁盘块位置上，在做范围查询的时候会导致较高的磁盘IO，以致严重影响到性能。

 

三、日志结构合并树LSM-tree(Log-Structured Merge-Tree)

众所周知，数据库的数据大多存储在磁盘上，而无论是传统的机械硬盘(HDD Hard Disk Drive)还是固态硬盘(SSD Solid State Drive,SSD)，对磁盘数据的顺序读写速度都远高于随机读写。

然而，基于B+树的索引结构是违背上述磁盘基本特点的——它会需要较多的磁盘随机读写，

于是1992年名为日志结构(Log-Structured)的新型索引结构方法便应运而生。

日志结构方法的主要思想是将磁盘看做一个大的日志，每次都将新数据和索引结构添加到日志的最末端，以实现对磁盘的顺序操作，从而提高索引性能。不过日志结构方法也有明显的缺点，随机读取数据时效率很低。

1996年，一篇名为The log-structured merge-tree(LSM-tree)的论文创造性地提出了日志结构合并树(Log-Structured Merge-Tree)的概念，该方法既吸收了日志结构方法的优点，又通过将数据文件预排序克服了日志结构方法随机读性能较差的问题。

直到10年后的2006年谷歌的Bigtable论文使用LSM-Tree技术开始流行。随后2007年的HBase与2008年的Cassandra在LSM-Tree思想基础上诞生，极大推广了LSM-tree技术。

 

LSM-tree的核心思想是同时使用两部分类树的数据结构来存储数据，并同时提供查询。其中一部分数据结构存在内存缓存(memtable)负责插入更新和读请求，并在内存中进行排序；另一部分写在磁盘(sstable),负责读操作，有序且不能更改。

使用日志文件做数据恢复保障，所有操作记录先写Log，再写memtable，最后冲写到sstable

定期合并小sstable以减少sstable数量，对每个sstable使用布隆过滤器，以加速数据存在与否的判定，从而减少数据的总查询时间。

 

 

索引

提高数据库查找速度的关键之一是减少磁盘的访问次数，并采用树形结构做索引

 

二叉查找树和平衡二叉树

二叉查找树在极端非平衡情况下查询效率会退化到O(N),因此尝试采用平衡二叉树；但是平衡二叉树的树高为:

log2 N

 

树高越高，查询次数越多越慢。同时，每次访问磁盘会读取多个扇区的数据，远大于单个树节点的值，造成浪费

 

B+树

传统关系型数据库的常用结构。

 

每个树节点只放键值，不放数值，叶子节点存放数值，使得树高度较低

 

叶子节点按值大小顺序排序，带指向相邻节点的指针，方便区间数据查询

 

从叶子节点开始更新，以较小的代价实现自平衡

 

缺点是随着数据插入，叶子节点会分裂，导致连续数据被存放在不同的物理磁盘块上，导致较大的IO开销

 

日志结构合并树（LSM）

日志结构的所有方式的将磁盘看做一个大的日志，每次都将新数据和索引结构添加到最末端；LSM通过将数据文件预排序解决了日志结构随机读性能差的问题。

 

使用两颗树来存储数据，其中一部分数据结构存在内存负责插入更新和读请求，并在内存中进行排序；另一部分写在磁盘,负责读操作，有序且不能更改

 

使用日志文件做数据恢复保障，所有操作记录先写Log，再写memtable，最后冲写到sstable

 

定期合并小sstable以减少sstable数量，对每个sstable使用布隆过滤器，以加速数据存在与否的判定