CHEN Jian's Java Blog

单维度索引是一棵B-树。如果一个索引由多个key组成，是一个Multidimensional Index（多维索引），该怎么办？ 基本的方法是建一个Index of Index.  确切地说，是为第一个属性建立一个B-树，这棵树的叶子结点指向的不是记录，而是第二个属性的B-树，第二属性的B-树叶结点指向的才是记录(如果还有第三属性，则第二属性树的叶结点指向第三个属性的B-树) 举个简化的例子。假设第一属性是性别，第二属性是年龄。 最终的树就是：(前两列代表索引项，最右一列是记录） 男 老 德华 少 冠希 女 老 嘉玲 少 阿娇 可以看出，第一属性只有一棵索引树；第二属性则有多棵索引树，第一属性的每个叶结点都会挂一棵第二属性的索引树。 查询的效率，取决于它有没有指定第一属性的值。如果指定了，就可以从唯一的第一属性的索引树中沿树根而下； 如果没有，就要遍历每棵第二属性索引树，性能会差很多。

dense index(稠密索引）：每条记录都建了一个索引项。如果表中有1,2,…10这10条记录，那么索引文件中也有1,2,…10这个10个索引项。 sparse index(辅助索引）：只有部分记录建立了索引项，具体来说，是为数据文件的每个block建立一个索引。 比如，1,2…10条记录在索引文件中只有1,5,9这3个索引项，其中项5指向 5,6,7,8这4条记录所在的block. 使用sparse index查找记录“6”时，先从索引文件中找到"5"这一项，然后找到记录5,6,7,8所在的block, 最后再从这个block内部找到记录"6".  可见，sparse index占用的空间会小一些，但查询时间由于加上了block内部查询的时间，所以会长一些。 而且，sparse index还要求数据文件已经排序，保证记录6,7,8在记录5的同一block中，否则，查到5所在的block后，在block内部仍然找不到6.

首先，一条数据库记录会有一个header, 存储本记录的长度，并包含一个指向table schema的指针。如果记录里中包含不定长字段(如varchar)，则在header中还应存储这些不定长字段的offset和实际长度. 典型情况下，一个block可以存储一个以上记录(下面会提到记录过大的情况). 为了记录每条记录在block内部的offset，可以在block header存放这些信息(当然，不是一定要放在header里)。各条记录的offset目录称作offset table. 这时，一条记录的地址 = block的物理地址 + 记录在block中的offset 插入记录时，如果记录顺序不重要，则直接插入一个block的空闲处或另找一个新block>，并更新offset table. 如果记录顺序重要，则找到应该放置此记录的block, 插入记录，并在必要的情况下滑动block内部分记录以保持顺序；如果当前block内的空闲空间不足，先插入，再把溢出的其他记录放到下一个block中，或者专门分配一个新block来存放，这个新block称为overflow bock, 当前block的header中会有一个指针指向它。 删除记录时，可以滑动块内的部分记录，填补空白以节省空间。那么原先指向本记录的指针，是不是就会指向新入驻的记录？ 为了避免这种情况下，删除记录后应该将offset table中的相应表项处设置一个tombstone, 指向本记录的指针发现记录指向了tombstone, 就知道记录已被删除。 修改记录时，如果记录是定长的，则直接修改，不需要额外动作； 否则，就要像增删一样考虑新记录过长和以及新记录变短时填补空白的问题。 p.s. 如果记录太大，则可能需要跨block存放(spanned record).  这时一条记录在N个block中各有一个fragment. 在这种记录下，记录的header中需要标识自己是一条完整的记录，还只是一个fragment; 如果是fragment, 还需要存储指向下一个fragment或其他fragment的指针

一个disk controller挂接多个disk，可以增加数据读写性能。具体两种方案： 1. 不同disk放不同数据。一个请求可以拆成N个请求分别执行。比如一个查询100行记录的请求，可以拆成4个请求，分别到4个数据库中去并行执行。 并行化后，总的时延就相当于子请求的时延。由于子请求需要读取的blocks变少，相应的seek time和rotational latency都可能小；总结下来，整体请求的时延也会变小。 2. Mirroring Disks.  所有disk的数据都是一样的，N个独立的请求可以分散落到N个disk中，虽然提升不了单个请求的时延，但在高并发情况下可以提高吞吐量。但它有一个缺点：write latency比较高，因为写数据时需要将数据写到各个disk中。

查询数据库时，整行查询或者查询一行中多个字段的概率很高。 如果不同字段分布在不同block中，那么这次查询就要读取多个block. 1. 由于磁盘读取是以block为最小单位的，读取多个block意味比起只读一个block要多读出很多数据，增加transfer time不说，还会浪费内存。 2. 如果这些block不是连续的，那还会增加磁盘的seek time和rotational latency （ 术语解释) 上面是读，写其实也是一样的。 推论： 1. 如果一行记录需要跨多个block, 也应该选择同一个track上的blocks(只有一次rotational latency) 或者同一个cylinder上的多个 blocks(只有一次seek time) 2. 如果多行记录被同时取出的概率很高，也应该如上安排，放在一起。