索引优化¶

索引¶

联表时，MySQL 可以使用索引。但是对应列需要类型和长度相同，其中，VARCHAR 和 CHAR 视为同类型。并且，对于非二进制字符列，两者的字符集也要相同。

对数据量小的表，索引的优化有限。对数据量大的表，如果查询绝大部分数据，顺序读取可能会更好。

对于 \(n\) 阶的 B+树，每个结点至多有 \(n\) 个子结点，至少半满，即有 \(\lceil \frac{n}{2} \rceil\) 个子结点，如果结点有 \(k\) 个子结点，则其必有 \(k-1\) 个关键字。

B+树比二叉树优势在于，B+树的结点很大，可以包含大量关键字和子结点指针，比较胖而矮，那么查询时，从根到叶子结点的长度更短，减少了对磁盘 I/O 次数。

B+树中插入新值的过程是自底向上的。如果过程中某个结点已满，先尝试将一些项重新分布到相邻结点中。如果相邻结点本身已满，则将该结点和相邻结点分裂为三个结点，并均匀分配关键字或记录，新节点大约是 \(\frac{2}{3}\) 满的。

B+树中删除值的过程也是自底向上的。如果结点的项数少于 \(\lfloor \frac{2n}{3} \rfloor\)，先尝试从相邻的结点中借入一项。如果两个兄弟结点都只有 \(\lfloor \frac{2n}{3} \rfloor\) 项，则将该结点和两个兄弟结点合并为两个结点。

尽管 B+树的插入和删除操作比较复杂，但它们需要较少的 I/O 操作。最坏情况下，一次插入或删除的 I/O 操作次数为 \(O(\log_{\lceil \frac{n}{2} \rceil}{N})\).

在 B+树索引中，树的叶子结点直接存储记录，而不是指向记录的指针。尽管比非叶子结点中存储的指针数目少，但仍要求至少半满。

在最初组织时，树上连续的叶子结点可以存储在连续的磁盘块中，这样对叶子结点的顺序扫描也相当于在磁盘上的顺序扫描。随着插入和删除操作，叶子结点可能不连续，也许需要对索引进行重建。

如果在辅助索引中存储指向记录的指针，那么记录更新时，辅助索引都需要更新。因此，在辅助索引中，不存储指向记录的指针，而是存储主索引关键字。这个方法减少了文件重组导致的索引更新的代价，但是增加了回表的操作。