一文帮你理解MySQL索引原理，不容错过的深度好文

书到用时方恨少，大概只有面对就业面试的时候，程序员们才会发出这样的感慨。面对回答不上的各种技术题，应聘者除了尴尬的笑着再无其它。如何改变这种局面呢？如何在面试过程中侃侃而谈，这绝对是关系到程序员就业的一大重要环节，今天，将揭开那些在面试中侃侃而谈程序员们的面貌，告诉你什么才是一个合格的程序员？

对于PHP工程师而言，掌握MySQL索引是通往中高级工程师的必学类目。目前大部分数据库系统及文件系统都采用B-Tree(B树)或其变种B+Tree(B+树)作为索引结构。B+Tree是数据库系统实现索引的首选数据结构。

什么是B-Tree(B树）？

B树是一种多路搜索树。定义任意非叶子结点最多只有M个儿子，且M>2。根结点的儿子数为[2, M]。除根结点以外的非叶子结点的儿子数为[M/2, M]。每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）。非叶子结点的关键字个数=指向儿子的指针个数-1。非叶子结点的关键字：K[1], K[2], …, K[M-1]，且K[i] <= K[i+1]。非叶子结点的指针：P[1], P[2], …,P[M]（其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树）。所有叶子结点位于同一层。

什么是B+Tree(B+树)？

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。总结说来，B+树是B树的一种变形树。

他们之间的差异在于：非叶子结点的子树指针与关键字个数相同。非叶子结点的子树指针P[i]，指向关键字值属于[K[i],K[i+1])的子树。为所有叶子结点增加一个链指针。所有关键字都在叶子结点出现。

为什么说B树和B+树可以做索引呢？原因又是什么？

因为在B-Tree中查找，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。在实际实现中，每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次I/O。B树中一次检索最多需要h-1次I/O（根节点常驻内存）。一般实际应用中，出度d（树的分叉数）是非常大的数字，通常超过100；h非常小，通常不超过3。

所以说相对于其他树结构而言，用B树作为索引结构效率是非常高的，更不说在B树上优化的B+树。

通过以上述说，你明白数据库的索引了吗？