仍然是第三章

B树

上学的时候应该就学过，相对于LSM-Tree来说，熟悉的多了，大多数db也是用B树的。B树本身就不写了。
B树把数据库分成大小固定的block或者page。一般4kb，但是有时也大一些。每个page有自己的地址，所以一个page可以refer另一个page，类似再内存中的指针，但是这些都是在disk上的，这样就形成了一个B-tree。对每个页，每次读写一整个页到内存进行操作。

branch factor是B树的度，代表有多少个子节点，一般来说是几百个。

查找操作中，一层层找到叶节点，里面存着数据或者存着去哪里找这个数据（根据这个是索引的类型，后面说）。
对于写更新操作，找到那个有数据的叶节点，更新掉，然后写会disk。如果是加入新值。那就是分裂节点操作，具体B数的实现。

一般来说B层数也就3-4层。一个500度的B数，4层，page：4kb，可以存在256T的数据。500^4 * 4kb ~= 250T

让B树更reliable

每次更新操作，是inplace的写盘，有的操作甚至会设计到多次写盘，如果说再修改过程中，crash了，那就gg，啥都乱了。为了应对这种事情，需要有一个另外的data structure存在disk上，write-ahead log（这个就是WAL，也叫sqlserver立叫redo）每次修改Btree的操作都需要写在这个append-only的file里，这样在恢复的时候，依靠这个来恢复btree的consistent state。
另外在concurrency方面，为了防止对同一个page进行读写看到inconsistent的state，用latches（一种轻量级的锁）来保护。这里LSM-Tree就有优势了，因为他们不存在这种问题。

（对于WAL（redo）和latches这里没有展开说，要了解更多需要自己去找更多资料，之后打算研究下mysql，postgresql应该会涉及到这些细节）

B-Trees LSM-Trees的比较

BT读的速度快过LSMT，但是写的速度LSMT肯定是快的。
LSMT写内存和一次disk log，BT写log和整个page（即使），两次写disk（提到innodb两次写page。。）
LSMT因为都是顺序写，顺序compact，disk fragment比BT的少。
LSMT后台需要不断merge和compact，就到只了写放大的问题，在数据量大/写的速度很快，这个时候就后台的进程和实际请求就会争抢disk的带宽，会导致读写有长尾请求，也费disk。相对而言，BT不存在写放大，所以相对wr都很稳定可预测。
BT是一个key就在一个位置，LSMT可能存在多个sst里面，所以BT有更强的consistence，在需要对多个key加锁的情况下，BT更容易。

主索引，次索引，聚簇索引，非聚簇索引。

主索引我觉得是一个中文翻译的问题，因为应该是primary key index，primary key都是唯一的。
聚簇索引是database的物理页真的是按照这个索引的顺序来排列的。
注意primary key index != 聚簇索引。
在mysql里默认primary key 上做聚簇索引，所以在disk上的的确确按照primary key来排列。但是sql server可以指定非主键的列来做聚簇索引。这时候非主键的索引是聚簇索引，primary key 会默认加一个非聚簇索引，为啥还需要这个主键的非聚簇索引呢？为了保证主键唯一，当然这时候聚簇索引也需要唯一。
次索引就是非主键索引，一般可以有重复，而且都是非聚簇索引。

所以我觉得在平时的时候就说聚簇和非聚簇，这样更不容易有歧义。
聚簇索引，里面存的就是实实在在的数据，但是非聚簇索引呢，里面存的可以是一个完整数据的拷贝。也可以是指向一个堆文件里的内容（heap file），堆文件存着一个数据的拷贝，这样在多个非聚簇索引同时存在的时候，都可以指向那个heap file。在update的时候，如果能inplace的update这个拷贝，索引都不需要动。在mysql的innodb里，采用的是另外一个方法，不指向堆文件，而是指向的是primary key，这样在读的时候其实是一次跳转，从当前这个key，跳到主键对应的整个row，然后再拿到需要的数据。
当然，在非聚簇索引中，除了要索引的那个列，也可以放一些其他的，这样在查询的时候就不需要再跳转到heap file或者主索引。这样加快了读速度，但是同时也增加了disk的空间。