索引——数据库中又一个面试常考的内容（1）

当我们系统的学习了数据行的CRUD操作以后尤其是查询是四者之中最复杂的于是我们就想高效地查询、更新表中的数据索引就应运而生了。为什么要使用索引一句话就是提升查询效率。MYSQL数据库要实现的两个关键目标安全、效率。而安全优先的情况下就要考虑效率了。索引应该选择哪种数据结构HASH表时间复杂度是O(1)因此查询速度非常快但由于HASH不支持范围查找所以MYSQL没有选择这个哈希表。二叉树二叉树的中序遍历是一个有序数列因此它支持范围查找但当最坏情况下会退化成一个单边树即后来的数据都比根节点的树大或小时时间复杂度为O(n)并且在节点个数过多的时候树高无法保证由于磁盘IO是制约数据库性能的主要因素由于数据库中的数据是在磁盘中保存的每一次访问子节点都有发生一次磁盘IO因此磁盘消耗过大效率很低。N叉树这个就是为了优化二叉树的树高而设计的假设N叉树的度为4我们在树中添加若干个数据如图可以看到这里的树高被有效的控制了时间复杂度也是O(logN)在数据量相同的情况下可以有效的控制树高也就是说可以使用更少的IO次数来查询目标节点大大提高了查询效率。可是这个数据结构仍然没有被使用而是用了B树。B树B树是一种经常用于数据库和文件系统的平衡查找树同样以4阶B树为例如图所示这个的时间复杂度也是O(logN)但与N叉树不同的是叶子节点那里有了小箭头其实那是链表并且是双向链表所以还是双向的链表是不是很神奇这时候有人会问不是B树吗那么B树与B树有什么区别呢如图是B树B树与B树对比1.MYSQL用双向链表来组织叶子节点因此叶子节点之间有一个相互连接的作用可以根据一个叶子节点来查询与他相邻的兄弟节点2.观察B树的根节点与叶子节点时可以发现根节点的值都包含在叶子节点之中但MYSQL的B树的根节点只起到保存对子节点的引用的作用并不存储实际数据真正保存实际数据的是子节点3.对于B树而言相同树高的情况下查找任一元素的时间复杂度都相同性能均衡。对于第二条例如我想查询60的具体位置从最上面的根节点开始发现比70小那么就去根节点左下引用比70小的根节点找又发现比50大就去其右下的子节点中找最终在第三个子节点的第二个数据中找到了他。由于内容过多我们下次再讲关于索引的内容再见。