数据库索引结构的选择
本身这部分知识不是很难，平时听着也就听着了，知识很零散，总结一下给自己。
1. 磁盘数据库
磁盘数据库中，例如MySQL，Oracle，每张表的数据实际上都是存在磁盘中的。每张表的表头都存储了这张表的索引信息。磁盘文件的索引结构的银弹是B+树，B+树的优点有如下几点：（1）非叶子节点中不存卫星数据，聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（二级索引）中，叶子节点带有指向卫星数据的指针。这样的方式使得查询每次都要查到叶子节点，查询性能更加稳定。这点跟B树不一样，B树的查询性能不稳定，因为非叶子节点中也有卫星数据。（2）范围查询更加高效，叶子节点形成有序链表。同样，如果要在B树索引上范围扫描，需要读取更多的节点。（3）结构本身“矮胖”，disk-IO次数更少。相比于二叉树，每个节点包含多个元素，层数少，因此一次查询需要读取的节点数少。
关于为什么B+树对磁盘数据库友好，以及和B树的区别，可以参考以下两篇文章，写的很清楚。
为了说明B+树作为磁盘数据库索引结构是如何工作的，举个例子。
当client需要查询某张表的某行数据时，分为两种情况：（1）根据主键查询；（2）根据非主键列查询。
（1）主键查询。一般对主键列建立的索引都是聚集索引，即该索引中键值的逻辑顺序决定了表中相应行的物理顺序。B+树索引的根节点一般存储在内存中，因为每次查询操作都需要访问。根据根节点获取到第一层索引节点，并从该表的文件头中加载进内存，这是第一次IO。重复此过程直到访问到叶子节点，读取出该节点存储的卫星数据。B+树的高度大概在3-4左右，所以查询一次磁盘上的数据需要3-4次IO。
（2）非主键查询。如果该非主键列上有索引表，则先通过索引表B+树获取到行的卫星数据的指针，接着去读取数据，这个过程与主键查询是一致的，不过按照非主键列构建的B+树索引，其键值的逻辑顺序肯定与表的实际物理顺序不一致，因此这个索引是非聚集索引。
2. 内存数据库
数据如果都存在内存中，B+树就没有那么必要了，因为读取B+树节点不再是磁盘IO操作，而只是内存读取操作，时间很短。
（1）B-树
Balance-tree，B-树相比于二叉树来说，它是balance的，即，如果要增加或删除一个数据，二叉树的改动会非常大，但是B-树只需要改动几个节点就能再次达到平衡。能够保持较稳定的性能。
（2）skiplist
简单来说，跳表的原理是，在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。它的缺点在于对CPU不是很友好，因为跳表需要不断做指针跳转，每一次指针跳的时候都可会发现数据在缓冲区中不命中。
（3）Bw-tree, masstree
总之，在内存数据库中使用B-树还是跳表是有争议，新的结构如，Bw-tree, masstree的出现，在挑战B-树的地位。
3. LSM架构
把这种架构的数据索引结构单独拎出来是因为这种架构中的索引结构是多层的。LSM架构中基线数据放在磁盘中，增量数据放在内存中，当内存中的增量数据过大时，需要先转储到本地磁盘，之后再与基线数据合并。相比于传统的磁盘数据库，写性能得到了提升，但是损失了读性能（读操作需要合并增量与基线数据）。索引结构有内存的B-树，转储的表索引和合并后的表索引。磁盘上存储的表的索引结构都放到的表文件的头部。此外，为了更快的定位到数据，可能还会使用多级索引，如ob的宏块，微块。
