Month: July 2014

可以用Hash Table做数据库索引结构，一个bucket是一个block链表。 性能: 1. 如果每个bucket都只有一个block, 那么增、删、查都只有一两次block读写(增、删需要先读再写)，即一两次磁盘i/o. 这比其他各种索引都好的多。 2. 如果某个bucket有很多block, 不用说，发生在这个bucket上读写性能会很差。 3. 另外，这种索引对Range Query没有支持。

关系数据库中的索引一般使用B+树结构（或其变体）   有几点值得一说： 1. B是”Balanced”的意思，意即从树根到所有树叶的路径都一样长 2. 图中每个结点都是一个磁盘block 3. 叶结点中向下的箭头指向数据记录 4. 增删记录时可能会导致结点的递归分裂或合并 5. 每个叶节点的最右边有一个指针指向下一个更大的索引项所在的叶结点 性能： 1. 增、删、查（单条记录）的I/O次数约等于树的层高 2. 树的层数取决于记录数和每个block可以存放的索引项的数目（这个数目也决定了一个结点可以有多少个子结点）。如果block大小=4k, 索引字段类型是整型，那么一个3层的B-树可以索引1500多万的记录数(具体算法参见hector garcia-molina《数据库系统实现)。 也就是说，大部分情况下，三层就够了。 3. 每个叶节点的最右边的指针可以使Range Query成为可能(即范围查询,  key between 100 and 200 这种)。

稠密、非唯一索引可能导致索引文件在存储空间上的浪费。举个例子，key=’中华民国是华人骄傲’ (多达9个字符)的记录有多少条，为它建立的索引项就有多少条。 有个解决办法是在索引项中为每条相应的记录开辟一个指针。这样key=’中华民国是华人骄傲’的索引项只须维护一份，原大量索引项所占的空间变成大量指针所占的空间。一般来说指针所占空间比较小，所以可以节省不少空间。 但是索引项中增加大量指针会使索引项本身的大小过于膨胀，这会影响索引扫描时的I/O速度(需要读更多block)。为了解决这个问题，我们可以专门使用一块空间集中存放所有索引项的指针集合。 这个在索引和数据之间的指针大集合称为 “bucket” (桶). 搜索引擎中常用的inverted index(倒排索引)，由于key的重复率特别高，就会经常使用bucket这种机制.

1. 索引文件是有序的，查找时可以用二分法或其他基于树型结构的查找法; 而记录文件不一定有序，时间复杂度可能等于记录数。 2. 索引文件存储字段较少，占用的block数比数据文件少，在索引文件中遍历，所需的I/O时间会短很多。 3. 索引文件如果足够小，可以直接放内存里，这样遍历起来就更快了。

data file一般是顺序文件(sequential file), 也就是说在磁盘中这个文件内部是按某个key排序的。 primary index(主索引)的key就是顺序文件的key.  主索引文件的排序方式与数据文件的排序方式相同. 如果要根据primary index查找key=6的记录，由于排序方式相同，你会发现所有key=6的记录都在一个block中或者几个连续的block中。 而secondary index(副索引)没有这个特性，它的key不是顺序文件的排序key, 也就是说副索引文件的排序方式与数据文件的排序方式并不一致。如果根据secondary index查找key=6的记录，由于排序方式不同，你会发现所有key=6的记录未必在同一个block中，也未必在几个连续的block中。 可以看出，使用secondary index对非唯一性字段进行查找时，由于目标记录不在同一个block中，也不在连续的几个block中，磁盘I/O的时间比起基于primary index的查找过程会多很多。 同理可知，对于范围查找如 key between 7 and 10,  secondary index 也有相同的劣势。

顾名思义，data file(数据文件）存放一个关系的数据，index file存放索引。 一个data file可以对应多个index file，正如一张表上可以建多个索引。 要注意的事，这里的一个"file"未必就是操作系统中的一个文件。两者概念类似，但不是同一个东西。

单维度索引是一棵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的指针