mysql数据库之索引详细介绍-木庄网络博客

本文整理自网络，侵删。

思维导图

简单理解

你可以把索引理解为一本书的目录，我们可以通过索引快速的找到我们需要的数据，大概就像下面这个图，索引就像是右边的二叉树，每个节点指向具体的数据的物理地址，先通过二叉树找到数据的位置，然后再去物理磁盘中获取数据。

但是不同的二叉树的特性不同，我们还要选择合适的树来作为索引，所以接下来就来学习一下各个树的特性

索引模型的演变

二叉查找树

二分查找树就是在数组的基础上，利用二分查找技巧，将用到的中间节点，作为指针。这样他的每个节点的左子树的值都小于该节点的值，每个节点右子树的值都大于该节点的值。在查找元素时，我们于根节点进行对比后，就能每次近乎一半的去除掉查找范围，可以极大的加快查找速度。

优点：

插入方便，不必连续排列

利用树的特新，查找很方便

缺点：

如果每次都是插入都是最大值，会导致其变成链表，查找复杂度增加

插入的元素越多，树的高度就会高，导致查询性能下降

自平衡二叉树

相比于二叉树来说，自平衡二叉树会通过左旋或者右旋来保证左子树跟右子树的高度差不超过一。这就很好解决了二分查找树变成链表的问题

?但如果元素越多，树的高度还是很容易变的很高，这会导致查询效率变慢。为了解决这个问题，于是就出现了B树。

B树

B树的最大不同就是不再限制一个节点只有一个节点，而是允许有多个节点，这就是多叉树。并且B树所有的叶子节点必须在同一层次，也就是它们具有相同的深度

例如一个度为 d 的 B-Tree，设其索引 N 个 key，则其树高 h 的上限为 logn(N/2)，检索一个 key，其查找节点个数的渐进复杂度为 O(logn((N+1)/2))。从这点可以看出，B-Tree 是一个非常有效率的索引数据结构。

局部性原理

????????而这种多个节点的结构，还可以很好的借助磁盘预读的特性。

????????由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘 I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高 I/O 效率。

????????在B树中，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B树还需要使用如下技巧：<br />每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次I/O。

阅读剩余部分