MYSQL索引数据结构

数据库为何要使用索引?

• 磁盘IO的方式
  寻道（速度较慢）,旋转（速度较快）。
  一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

磁盘IO.png

• 局部性原理与磁盘预读
  磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分，寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台500 -MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。这种情况下，我们就需要对其进行优化。
  FIX：向表插入数据的时候，在磁盘上面是分开分布的，并不连续在一起的。极限情况下，找到一某一行数据可能要经过最大行数的IO。

索引是什么?

• 索引的作用
  帮助Mysql高效获取数据的排好序的数据结构。
• 索引的存储
  索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。
  与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。
  FIX：mysql data目录下的数据库里面的表文件打开，可以发现专门存储索引的文件。

索引的数据结构，优劣势对比

二叉树

二叉排序树.png

• 二叉排序树
  ①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  ②若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
  ③左、右子树也分别为二叉排序树；
  当插入的元素是有序的，生成的二叉排序树就是一个链表，这种情况下，需要遍历全部元素才行。如果我们可以保证二叉排序树不出现上面提到的极端情况（插入的元素是有序的，导致变成一个链表），就可以保证很高的效率了（效率近似于折半查找）。
• 平衡二叉树
  ①平衡二叉树要么是一棵空树，要么保证左右子树的高度之差不大于 1。
  ②子树也必须是一颗平衡二叉树。
  用平衡因子差值判断是否平衡并通过旋转来实现平衡。
  平衡二叉树在添加和删除时需要进行旋转保持整个树的平衡。
  解决的问题：通过维护树的平衡来避免生成二叉树为链表的情况。
  缺点：维护这种高度平衡所付出的代价比从后者那个获得的效率收益要大，故而实际的应用不多。但在对插入删除不频繁，只对查找要求较高，平衡二叉树的优势还是比较明显。

• 红黑树
  一种自平衡的二叉查找树，调整方式（变色，旋转[左旋转][右旋转]）节点是红色或者黑色。
  根节点是黑色，每个叶子节点都是黑色的空节点。
  每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
  解决问题：
  缺点：每个节点只有两个子节点，当数据量大的时候深度不可控。
  FIX:TreeMap底层就是红黑树，有兴趣的朋友可以了解一下。

HASH
通过算法，将索引和磁盘的地址进行关联，查找某一行数据便只需要进行一次IO即可。HASH索引无法实现范围查找，但是匹配具体条件查询的话效率还是比较高的
BTREE

B-TREE.png
B+TREE.png

• B-TREE
  KEY和指针互相间隔，节点两端是指针,每个指针要么为null，要么指向另外一个节点。
  叶子节点具有相同的深度，叶子节点的指针为空，节点中的数据key从左到右递增排列。
  度（节点存储数据的个数）> 15/16的时候会分裂，横向扩展。
  检索原理：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或未找到节点返回null指针。
• B+TREE
  非叶子节点不存储data，只存储索引key；只有叶子节点才存储data

MYSQL的B+TREE

MYSQL B+TREE索引结构.png

在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。这样就提高了区间访问性能：如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率(无需返回上层父节点重复遍历查找减少IO操作)。

MYSQL索引底层数据结构分析

MyISAM引擎
非聚簇索引：myi索引文件和myd数据文件分离，索引文件仅保存数据记录的指针地址。叶子节点data域存储指向数据记录的指针地址。(底层存储文件： frm -表定义、 myi -myisam索引、 myd-myisam数据)。可以看到表定义文件，索引文件，数据文件是分开的
MyISAM引擎的表，索引可以缓存到内存中。

MyISAM引擎索引.png

InnoDB引擎
聚簇索引：数据&索引文件为一个idb文件，表数据文件本身就是主索引，相邻的索引临近存储（数据一定也是相邻地存放在磁盘上）。 叶节点data域保存了完整的数据记录(数据[除主键id外其他列data]+主索引[索引key:表主键id])。 (底层存储结构: frm -表定义、 ibd: innoDB数据&索引文件)。聚簇索引的索引和数据是一个文件。

主键索引 & 辅助索引.png