数据库理念
数据库的两大核心能力：
- 把数据存进去。
- 把数据读出来。
评价一个数据库的优劣，有很多方面的考量，但是效率绝对是其中数据库产品最关注的核心之一。于是基于这两个功能，衍生出两个指标：
- TPS：Transaction Per Second
- QPS：Query Per Second
两者能皆高当然是最好，但世界上往往不会有win-win的事情，所以不同数据库，甚至同一个数据库的不同存储引擎会关注不同的指标从而通过差异化提高自己的竞争优势。
目前行业内通常就存在两种常见的数据库，RDBS和NoSql，前者如Oracle、Mysql等，后者如Mongo、Hbase等。
备注：redis其实不算传统意义上的数据库系统，因为它所有数据都存在内存中，没有所谓的磁盘数据存储结构、索引维护、ACID等特性。
LSM-tree
Log Structure Merge Tree：日志结构合并的树
在NoSql系统，通常采用LSM-tree作为数据和索引的存储方式，实际如名称所示，就是将磁盘划分为段，每段存储一些日志文件（一般是二进制数据），每当调用写操作时会从最新段中追加一条数据，这非常类似于Redis的AOF机制，所以在取一条数据的时候就需要将该key所有段中的数据捞出来进行merge后才能拿到最终数据，当然为了减少历史数据的合并成本，会有额外机制将过老的数据段永久合并。
可以看到，这种操作的好处就是写入效率非常搞，没有锁开销，索引开销极低。最重要还是这种追加存储的方式是顺序写，极大提高了写入效率。一般来说顺序写的效率是随机写的10倍以上，kafka和rocketmq的高效原因之一就是同样采用了追加写入数据的方式。
但是在读操作中增加了数据合并的成本，另外由于这种日志追加方式进行数据存储，只适合建立hashmap结构的索引数据
B-tree
在RDBS系统，通常采用B-tree的结构，首先它将数据存储和索引存储结构区分开来（主键索引除外），数据存储和上述差不多，也就是将磁盘划分成多个存储段，也叫存储页，一般是4K到16K不等，和LSM方式的区别在于，它是固定的大小，比如按16K一页划分且一行数据占用1K大小的话，那么一页可以存储16条数据，如果当前页的offset为100的话直观点就是id=100，那么插入一条id=117的数据会怎么样？你可能觉得会另起一页，但实际是会放在当前页，再来一条id=132呢，也一样会放在当前页，但是如果随着id=101~116的数据不断插入，当空间占满了16条数据后，当然一般来说不会到占满，而会在某个比例时就会发生页分裂的机制。分裂为两页，比如一页存储id=100~112数据（其余空间空闲），一页存储id=117和132数据（其余空间空闲）。
索引结构就是B树，首先它是一颗多叉树，由于树的特性保障了索引是有序的，优点是通过树的查询特性的进行单点和区间查询的效率都比较高，缺点有两个，一是需要在每条数据插入时都需要同步更新索引，如果索引越多成本越高，二是因为节点关联的指针值不变，所以数据更新时需要更新原有记录，而不能和LSM一样直接追加数据，也就是说这里是随机写。
B+树在B树的基础上优化了两点，一是在非叶子节点不存储实际数据，虽然增加了一次非叶子节点的回表操作，但是大大减少了非叶子节点的存储空间，使得一页能存储更多的索引数据，从而降低了层高，提高了效率。如果要问为什么一层只能有一页，可不可以有多页，也不是不行但存在一些问题，首先数据库的分页和操作系统的分页还不是同一个概念，前者只是应用软件层面的，后者是系统层面的，但后者是前者的基础，也就是说后者的查找不同分页是需要寻址成本的，我们都知道硬盘的随机寻址成本是10毫秒级别的（非常高），那么数据库的分页如果小于操作系统的分页大小，比如数据库是16K一页，操作系统的是32K一页，那么单次寻址能拿到2个数据库页，在这种情况下回答刚才那个问题，那就是可以多页，但一般情况是数据库的分页是大于操作系统分页大小的，再考虑到页是最小存储单元，也就是一次拿一数据库页已经是较高且必要的成本了。所以就回答那个问题，为什么要B+树要通过减少索引页的实际数据存储空间来存储更多索引数据，答案就是在空间大小一定的前提下，单页存储越多的索引越能减少寻址成本。第二个优化就是在叶子节点上，通过双向指针将所有叶子节点连接成本双向链表。减少了区间查询场景的下的中序回溯成本。
若有收获，就点个赞吧
0 人点赞
