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.
单维度索引是一棵B-树。如果一个索引由多个key组成，是一个Multidimensional Index（多维索引），该怎么办？ 基本的方法是建一个Index of Index. 确切地说，是为第一个属性建立一个B-树，这棵树的叶子结点指向的不是记录，而是第二个属性的B-树，第二属性的B-树叶结点指向的才是记录(如果还有第三属性，则第二属性树的叶结点指向第三个属性的B-树) 举个简化的例子。假设第一属性是性别，第二属性是年龄。 最终的树就是：(前两列代表索引项，最右一列是记录） 男 老 德华 少 冠希 女 老 嘉玲 少 阿娇 可以看出，第一属性只有一棵索引树；第二属性则有多棵索引树，第一属性的每个叶结点都会挂一棵第二属性的索引树。 查询的效率，取决于它有没有指定第一属性的值。如果指定了，就可以从唯一的第一属性的索引树中沿树根而下； 如果没有，就要遍历每棵第二属性索引树，性能会差很多。
顾名思义，data file(数据文件）存放一个关系的数据，index file存放索引。 一个data file可以对应多个index file，正如一张表上可以建多个索引。 要注意的事，这里的一个"file"未必就是操作系统中的一个文件。两者概念类似，但不是同一个东西。
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 也有相同的劣势。
1. 索引文件是有序的，查找时可以用二分法或其他基于树型结构的查找法; 而记录文件不一定有序，时间复杂度可能等于记录数。 2. 索引文件存储字段较少，占用的block数比数据文件少，在索引文件中遍历，所需的I/O时间会短很多。 3. 索引文件如果足够小，可以直接放内存里，这样遍历起来就更快了。
首先，一条数据库记录会有一个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. 如果多行记录被同时取出的概率很高，也应该如上安排，放在一起。
分库可以将数据库访问的压力分担到多个子库中，提升数据库读写的性能；但数据库一旦分库，上层的读写操作就必须考虑分库这一事实。比如说，要查询某条记录，查询条件除了业务上的条件，还应该把带上一个分库的键值对，好让你的分库框架找到这条记录所在的库。 我根据自己的项目经验稍微归纳一下。 核心准则：尽量让所有的访问都只落在一个分库里。如果要访问多个分库才能完成操作，那么访问性能会由于多次网络I/O而下降，在事务方面也很不方便。 推论 1. 所有的SQL都应该带上分库的键值对，以帮助系统路由到记录所在的分库。比如，你的论坛系统中的帖子是按版面ID分库的，那么在查询某个帖子的详情时也应该把这个贴子所在版面的ID放到SQL里。 2. 被分库表的子表如果需要分库的话，应该按同一维度分库，以保证某主记录的相关子记录跟它总是落在同一个分库中，以方便表连接和事务。 如果帖子是按版面ID分库的，那么一个版面下的所有帖子“赞”记录也都应该跟这个版面下的所有帖子放在同一个分库中； 否则你很难实现“找出某版面下前十个帖子及每个帖子前十个赞贴的人”和“在同一个事务中新增一条评论记录并且将帖子的评论数加1” 3. 存在表连接和事务的其他场合，也都应该尽量保证相关记录出现在同一个分库。 4. 分库数最好不要特别多，以节省万一要全库扫描时产生的成本。在某些情况下，你的查询可能就是要扫描所有分库，一次分库查询就是一次网络I/O，但如果查询次数不多，这样的性能往往也可以接受。所以如无必要，不要设置过高的分库数；可以通过“清理三个月前数据”等机制以控制全库的总记录数，这样一来所需的分库数也不太多。
冗余本应计算出来的数值 统计数值可以通过select count(*)临时计算出来，但这种计算可能比较耗时，所以可以直接在表中增加这样一个字段并在相应事件发生时更新。 比如一个贴子的赞数、评论数都可以直接作为帖子表的字段，新增赞、评论时再累进这些字段。在查询一批贴子时，可以不用任何附加SQL就可以拿到这批帖子的赞数和评论数。 还有个例子：“前十个赞本贴的人”，也可以拼成单条字符串放在帖子表中。 字段冗余 A表除了外键关联B表的主键，还冗余了B表的其他一些字段。 1. 这种策略一般用于避免表连接： 在很多场景下，只需要查询A表即可。 2. 约束：业务上规定被冗余的字段不会发生改变，否则，修改B表后还要把A表也改一下，代码中很容易遗漏这一点，这样做还会带来性能损失。 3. 不冗余，不代表一定要表连接。要冗余还是不冗余，可以参考这里。 整条记录冗余 A表和B表没有外键关系，而是“复制”关系。它们字段基本上一样，或者说一个是另一个的子集。 分库分表环境下常常需要这种策略，以便对单张表按多个维度进行拆分。 SNS中有个典型的例子： 关注关系。 我们既要查看一个人的偶像列表，又要查看一个人的粉丝列表。所以，当数据量大时，你既要按粉丝ID分库，又要按偶像ID分库。一个关系有两个分库维度，那就只好做两张表了。 最好用一些专门的数据复制中间件完成这种事情。这类复制逻辑非常简单，中间件一般能轻松支持； 使用中间件，也可以使这种冗余关系对上层透明，业务逻辑编写者不需要自己实现数据复制。