目录

1. 概念-索引是什么？

2. 索引的数据结构(索引模型)

2.1 二分查找：

2.2 二叉查找树（BST Binary Search Tree）：

2.3 平衡二叉树(AVL Tree Balanced binary search trees)

2.4 多路平衡查找树(B Tree Balanced Tree)

2.5 加强版多路平衡查找树(B+ Tree)

3. innodb如何存储索引和数据的？

3.1 索引分类

3.2 索引如何存储数据

4. 注意事项

---

1. 概念-索引是什么？

索引相当于一本书籍的目录，它是帮助数据库快速检索数据的一种数据结构。

维基百科的定义

数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中的数据。

索引的简单示例图：

索引的好处就是查询更快。比较如下：

没有索引：查询数据时只能从磁盘中按顺序读取数据，直到找到所需要的数据。

有索引：从索引中找到数据存储的位置，然后直接从磁盘位置读取数据。

2. 索引的数据结构(索引模型)

索引的数据结构是B+Tree树。

比较一下相关的数据结构的优缺点：

2.1 二分查找：

优点：针对于有序数组，等值查询和比较查询的效率非常高。

缺点：更新数据可能需要挪动大量的数据。

适用场景：静态存储的数据。

2.2 二叉查找树（BST Binary Search Tree）：

示例图：

特点：左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。

优点：既能实现快速查找，又能够实现快速插入

缺点：查询耗时和这棵树的深度相关。假设我们的数据构成二叉查找树后，正好是一棵斜树，那么就和顺序查找的效率是一样的。

2.3 平衡二叉树(AVL Tree Balanced binary search trees)

定义：左右子树深度差绝对值不能超过1.

如何平衡：AVL树在插入和更新数据的时执行了1系列的计算和操作(左旋、右旋)来保证树的平衡。

存储特点：每个节点需要存储键值、数据磁盘地址、子节点引用

优点：解决了二叉查找树极端的斜树情况。

缺点：每个节点存储的数据太少，如果数据较多，树的深度依然很大。

2.4 多路平衡查找树(B Tree Balanced Tree)

示例图：

特点：分叉数永远比关键字数多1

如何平衡：分裂和合并

2.5 加强版多路平衡查找树(B+ Tree)

示例图：(图片来源于百度图片)

特点：1.关键字数和路数相等 2. B+Tree的根节点和枝节点中都不存储数据，只有叶子节点才存储数据。

优势：

        1. 扫库、扫表能力更强

         2. B+ Tree 的磁盘读写能力更强

        3.排序能力更强

        4. 效率更加稳定(B+Tree永远是在叶子节点拿到数据，所以IO次数是稳定的)。

3. innodb如何存储索引和数据的？

在innodb中索引即数据。

3.1 索引分类

聚集索引：索引键值的逻辑顺序和表数据据行的物流存储顺序是一致的。

二级索引（辅助索引）：如果表有主键，那么主键索引就是聚集索引，其他的索引统一叫二级索引。

3.2 索引如何存储数据

主键索引存储了所有的数据。

二级索引并不会把完整记录在叶子节点放一份，因为这会带来额外的存储空间和计算浪费。二级索引的叶子节点存的是这条记录对应的主键的值。如果需要拿除索引和主键之外的值，需要再到主键索引的叶子节点拿到数据(这就是回表的概念)。

示例图：(图片来源于百度图片)

4. 注意事项

1.不要在频繁更新的列上建索引，因为会引起分裂和合并