深入理解Mysql索引底层数据结构与算法

一、索引数据结构二叉树，Hash，B+树详解

什么是索引？

面试的时候大家基本都回答，索引就像是字典的目录，通过定位的目录迅速的就能找到所对应的内容，这样回答可能比较片面。在我理解，索引是一种提高搜索效率散列存储的一种数据结构

为什么要使用索引？

在不使用索引的情况下，当一个表里面有上百万行数据的时候，查询某一条数据会导致扫描全表，一行数据一行数据的遍历，导致查询时间变长效率变低。而使用索引，我们知道索引是一种数据结构，如果以id作为索引字段，把id放在树上，那么就可以通过二分法快速的查询出来，提高效率。

mysql索引为什么使用B树或B+树

我们先从最简单的二分搜索树开始分析，层层递进。

二分搜索树

定义：

1.若它的左子树不为空，则左子树上所有结点的值均小于等于根结点的值；

2.若它的右子树不为空，则右子树上所有结点的值均大于等于根结点的值；

3.它的左右子树均为二分查找树。