33559 www.cs.usfca.edu//~galles/visualization/algorithms.html
对于数据产品，底层的存储体系结构直接决定了数据库的特性和使用方案。
RDBMS (关系数据库)使用b树和b树作为数据存储结构。 B树和B树的典型方案是用于关系数据库的索引(MySQL )
HBase使用LSM树。
二叉树所有节点最多有两个子节点。 节点的左指针指向小于关键字的子树，右指针指向大于关键字的子树。
b )根节点至少有两个子节点，每个节点有M-1个key，M-1和M key的子节点按升序排列的值介于M-1和M key对应的值之间，其它节点至少有M/2 下图是M=4的四阶b树。
根据B树的搜索根节点对节点中的关键字(有序)数组进行二分搜索，如果找到，则结束，否则进入查询关键字所属范围的子节点； 重复直到对应的儿子指针为空或已经成为叶的节点；
b树的特性：
关键词集合出现在整树分布的任意一个关键词，只出现在一个节点上； 搜索可能以非叶节点结束(树的所有节点都包含数据，与b树不同)； 其检索性能与在关键词全集内进行二分检索相同； 下面是插入b树的演示视频，依次插入：
B+树数据读取速度因素
由于传统的机械磁盘具有顺序读写高速化、随机读写低速化的访问特性，因此该特性对磁盘存储结构和算法的选择有很大的影响。
为了改善数据访问特性，文件系统或数据库系统通常会对数据进行排序和存储，从而加快数据的检索速度。 为此，您需要确保数据在不断更新、插入和删除后保持有序。 传统的关系数据库方法是将b树
B树是B树的变形，与B树的不同在于：
在具有n个子树节点中，包含n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。所有叶节点包括包括所有关键字的信息和指向包括这些关键字的记录的指针，其中叶子结点本身根据关键字的大小为33555333350 所有关键字在叶的节点上出现M=3的b树，如下图所示。
B树检索： B树也基本相同，不同之处在于http://www.Sina.com/(B-树可以在非叶节点命中)，其性能也与在关键字全集中进行一次二分检索相同；
自小而大顺序链接。
非叶节点相当于叶节点的索引(稀疏索引)，叶节点相当于存储数据的数据层； B因为树叶的节点都是链接的，所以整个树的扫描只需对树叶的节点进行一次直线扫描即可。 另外，由于数据按顺序排列连接，所以区间的检索和检索很容易。 在b树中，必须递归遍历所有层次。 由于相邻元素在内存中可能不相邻，所以缓存命中性能不如b树好。 B树的原理是，B树在查询中应该不会变慢，但是如果数据的插入是无序的，比如插入跨度大的数据，比如5到10000，再比如3到800，就需要先“找到这个数据应该插入的位置” 如果此位置检测过程非常离散，则意味着每次搜索都没有子节点在内存中，此时必须使用磁盘查找时间进行搜索。 更新与插入基本相同
与b树相比，b树/B树插入12.34-5.67-8
插入b树，1 2 3 4 5 6 7 8
b树：
b树：
B+树只有达到叶子结点才命中
b树的关键字集合分布在整棵树上，叶节点不包含任何关键字信息，而b树的关键字集合分布在叶节点上，非叶节点只是叶节点关键字的索引； b树中的任意一个关键字只出现在一个节点上，b树中的关键字必须出现在叶节点上，或者可能重复出现在非叶节点上；B+的特性：)
b树仅适用于结构上，而b树适用于性能上； 树b的磁盘读/写成本更低。 关于b树随机检索，内部节点比b树小，能够存储在盘块中的节点中的关键字数越多，通过一次读入存储器而能够检索的关键字也越多，相对于此，进行IO读写IO读写次数是影响索引检索效率的最大因素。 B树的查询效率更稳定。 B树搜索有可能在非叶节点结束，离根节点越近的记录搜索时间越短，只要找到关键词就可以确定记录的存在，具有与在关键词全集内进行一次相同的性能
二分查找。而在B+树中，顺序检索比较明显，随机检索时，任何关键字的查找都必须走一条从根节点到叶节点的路，所有关键字的查找路径长度相同，导致每一个关键字的查询效率相当。（数据库索引采用B+树的主要原因是，）B-树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起，只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引？原因：相对于B树
（1）B+树空间利用率更高，可减少I/O次数，B+树的磁盘读写代价更低
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗。而因为B+树的内部节点只是作为索引使用，而不像B-树那样每个节点都需要存储硬盘指针。
也就是说：B+树中每个非叶节点没有指向某个关键字具体信息的指针，所以每一个节点可以存放更多的关键字数量，即一次性读入内存所需要查找的关键字也就越多，减少了I/O操作。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-树(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
（2）增删文件（节点）时，效率更高，
因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率。
B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
（3）B+树的查询效率更加稳定，
因为B+树的每次查询过程中，都需要遍历从根节点到叶子节点的某条路径。所有关键字的查询路径长度相同，导致每一次查询的效率相当。
由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
1. 索引在数据库中的作用
最基本的查询算法当然是顺序查找（linear search），遍历表然后逐行匹配行值是否等于待查找的关键字，其时间复杂度为O（n）。但时间复杂度为O（n）的算法规模小的表，负载轻的数据库，也能有好的性能。 但是数据增大的时候，时间复杂度为O（n）的算法显然是糟糕的，性能就很快下降了。
好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
索引是对数据库表 中一个或多个列的值进行排序的结构。与在表 中搜索所有的行相比，索引用指针 指向存储在表中指定列的数据值，然后根据指定的次序排列这些指针，有助于更快地获取信息。通常情 况下 ，只有当经常查询索引列中的数据时 ，才需要在表上创建索引。索引将占用磁盘空间，并且影响数 据更新的速度。但是在多数情况下 ，索引所带来的数据检索速度优势大大超过它的不足之处。
红黑树的性质：
红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。
具体性质如下：
每个节点颜色不是黑色，就是红色根节点是黑色的如果一个节点是红色，那么它的两个子节点就是黑色的（没有连续的红节点）对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点插入1 2 3 4 5 6 7 8
插入9后
LSM树：日志结构合并树(Log-Structured Merge-Tree)为了更好的说明LSM树的原理。以下举个极端的样例： 如果有1000个节点的随机key。对于磁盘来说，肯定是把这1000个节点顺序写入磁盘最快。可是这样一来，读就悲剧了，由于key在磁盘中全然无序。每次读取都要全扫描。
为了让读性能尽量高，数据在磁盘中必须得有序。这就是B+树的原理，可是写就悲剧了，由于会产生大量的随机IO，磁盘寻道速度跟不上。
LSM树本质上就是在读写之间取得平衡，和B+树相比，它牺牲了部分读性能。用来大幅提高写性能。
它的原理是把一颗大树拆分成N棵小树， 它首先写入到内存中（内存没有寻道速度的问题，随机写的性能得到大幅提升），在内存中构建一颗有序小树，随着小树越来越大，内存的小树会flush到磁盘上。当读时，由于不知道数据在哪棵小树上。因此必须遍历全部的小树，但在每颗小树内部数据是有序的。
LSM Tree ，这个概念就是结构化合并树的意思，它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中，而可以先将最新的数据插入内存中的树，驻留在内存中，当内存树的数据量超过设定阈值后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起)。合并操作会从左至右遍历内存中树的子节点 与 磁盘中树的子节点并进行合并，会用最新更新的数据覆盖旧的数据（或者记录为不同版本）。当被合并合并数据量达到磁盘的存储页大小时。会将合并后的数据持久化到磁盘，同时更新父节点对子节点的指针。
在LSM树上进行一次数据更新不需要磁盘访问，在内存即可完成，速度远快于B+树。当数据访问以写操作为主，而读操作则集中在最近写入的数据上时，使用LSM树可以极大程度地减少磁盘的访问次数，加快访问速度。
日志结构的合并树（LSM-tree）是一种基于硬盘的数据结构，与B+tree相比，能显著地减少硬盘磁盘臂的开销，并能在较长的时间提供对文件的高速插入（删除）。然而LSM-tree在某些情况下，特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于索引插入比检索更频繁的应用系统。
LSM树 读数据 磁盘中书的非子节点数据也被缓存到内存中。在需要进行读操作时，总是从内存中的排序树开始搜索，如果没有找到，就从磁盘上的排序树顺序查找。
LSM树 删除数据 。LSM树所有操作都是在内存中进行的，那么删除并不是物理删除。而是一个逻辑删除，会在被删除的数据上打上一个标签，当内存中的数据达到阈值的时候，会与内存中的其他数据一起顺序写入磁盘。 这种操作会占用一定空间，但是LSM-Tree 提供了一些机制回收这些空间。
合并前：
合并后：
合并前：
合并后：
简单来说，就是放弃磁盘读性能来换取写的顺序性。
1. 内存的速度超磁盘1000倍以上。而读取的性能提升，主要还是依靠内存命中率而非磁盘读的次数
2.写入不占用磁盘的io，读取就能获取更长时间的磁盘io使用权，从而也可以提升读取效率。
因此，虽然SSTable降低了了读的性能，但如果数据的读取命中率有保障的前提下，因为读取能够获得更多的磁盘io机会，因此读取性能基本没有降低，甚至还会有提升。而写入的性能则会获得较大幅度的提升，基本上是5~10倍左右。
Hbase中存储设计主要思想LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。
以上这些大概就是HBase存储的设计主要思想，这里分别对应说明下：
因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLogMemStore上的树达到一定大小之后，需要flush到HRegion磁盘中（一般是Hadoop DataNode），这样MemStore就变成了DataNode上的磁盘文件StoreFile，定期HRegionServer对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树，来增强读性能。hbase在实现中，是把整个内存在一定阈值后，flush到disk中，形成一个file，这个file的存储也就是一个小的B+树，因为hbase一般是部署在hdfs上，hdfs不支持对文件的update操作，所以hbase这么整体内存flush，而不是和磁盘中的小树merge update，这个设计也就能讲通了。内存flush到磁盘上的小树，定期也会合并成一个大树。整体上hbase就是用了lsm tree的思路。
https://blog.csdn.net/xushiyu1996818/article/details/90257422
图解 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html