谈谈对数据库索引的理解？

关于作者

• 作者介绍

---

---

B+树的存储特点：

局部性原理：

• 时间局部性:之前被查询过的数据很快可能被再次查询

• 空间局部性: 数据和程序都有聚集成群的倾向，具备某一个特点的数据经常聚集存储
• 磁盘预读:磁盘跟内存在进行交互的时候有一个最基本的逻辑单位，称之为页，每次在进行数据读取的时候一般读取的是页的整数倍，页的大小是跟操作系统相关，默认是4k或者8k，在mysql的innodb存储引繁中，默认是16kb

基于上述理论：数据读取的时候要分块读取，每次读取一部分数据，然后根据指针再次读取下一个块的数据。尽可能少的产生io次数，能读一次绝对不读两次尽可能少的读取数据，减少整体的io量。

为什么不使用哈希表做存储？

1. 必须要设计一个优秀的hash算法，保证你的数据足够散列，如果存在大量的hash冲突或者hash碰撞，那么会导致某些查询效率非常低。
2. 当需要进行范围查询的时候，需要挨个对比每一个元素值，效率极低，在生产环境中大部分的查询是范围
3. 空间问题：
   • hash比较浪费内存空间，而内存是非常宝贵的资源
   • memory存储引掌支持的是hash索引
   • innodb存储引擎支持自适应hash (由mysql自己来决定使用的是hash索引还是B+树索引，人为不能干预，由系统判断，只适用于innodb存储引擎)

为什么不使用二叉树、BST、AVL、红黑数？

每一个分支有且尽有两个子节点，当需要向其中插入更多的数据的时候，就必须要增加树的高度，而增加树的高度会导致树变深，会导致io的次数变多，所以所有的二叉树都是不建议使用的。根据结构不要求高，要求变胖，由此想到用多叉有序树，如B-树、B+树。

B树

实例图说明： 每个节点占用一个磁盘块， 一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为16和34, P1 指针指向的子树的数据范围为小于16, P2 指针指向的子树的数据范围为16~34。P3 指针指向的子树的数据范围为大于34。

查找关键字过程：

1. 根据根节点找到 磁盘块1 读入内存。[磁盘 /O操作第1次]
2. 比较关键字28在区间(16,34)。找到 磁盘块1 的指针P2。
3. 根据P2 指针找到 磁盘块3 ，读入内存。[磁盘 l/0操作第2次]
4. 比较关键字28在区间(25,31) 。找到 磁盘块3 的指针P2。
5. 根据P2指针找到 磁盘块8 ,读入内存。 [磁盘1/O操作第3次]
6. 在 磁盘块8 中的关键字列表中找到关键字28。

缺点：

1. 每个节点都有key，同时也包含data，而每个页存储空间是有限的，如果data比较大的话会导致每个节点存储的key数量变小。
2. 当存储的数据量很大的时候会导致深度较大，增大查询时磁盘io次数，进而影响查询性能。

B+树

B+Tree是在BTree的基础之上做了的一种优化，变化如下:

1. B+Tree每个节点可以包含更多的节点。这样做的原因有两个
   • 第一个原因是为了降低树的高度
   • 第二个原因是将数据范围变为多个区间，区间越多，数据检索越快
2. 非叶子节点存储key, 叶子节点存key和数据
3. 叶子节点两两指针相互连接(符合磁盘的预读特性)，顺序查询的性能更高

注意：在B+Tree上有两个头指针，一个指向根节点。另一个指向关键字最小的叶子节点。而且所有叶子节点(即数据节点)之间是一种链式 环结构。因此可以时B+Tree进行两种查询操作:一种是对于主键的查找和分页查找， 另一种是从根节点开始， 进行随机查找。

索引的使用场景和优化点

执行计划中，可以回表、索引覆盖、最左匹配、索引下推。