索引

• 索引是一种特殊的文件，包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引，并指定索引的类型，各类索引有各自的数据结构实现。

索引是干啥的？
一本书的目录，存在的意义，就是方便用户快速查找到某个东西在第几页~
类似，mysql的索引，也是为了方便查找~

mysql查找select的不足

select基本执行过程，遍历表，依次取出每个记录，然后再根据where字句的条件，决定这个记录要保留还是过滤。但是像这样的遍历本身效率是很低的。（尤其是数据量很大的时候)

mysql是把数据存储在硬盘上的，取出每个记录（这个操作都意味着访问硬盘）相比之下，就更希望访硬盘的次数能尽量少。

如何提高效率：

我们知道各类索引是通过不同的数据结构实现的，因此如果要提高效率，我们就要为索引选择最合适的数据结构。

数据库本质也是基于数据结构来实现的

二叉搜索树：

二叉搜索树：

它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

参考二叉搜索树博客：https://blog.csdn.net/qq_52988578/article/details/121402014

二叉搜索树可以提高搜索的效率，其时间复杂度为O(N)
但是这样的话，可以会存在单枝树，这样效率依然很低下

为解决这个问题因此产生了AVL树

AVL树

**AVL树的特点：**插入查找删除为O(logN)

AVL树本质上是一颗平衡二叉树
带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

• AVL树不会出现单枝树，因此提高了查找效率
• 但是这个时候又有新的问题

设定的AVL树，随着插入/删除元素的进行，这个AVL规则可能被破坏掉，这个时候就需要不断的调整树的结果，保证其符合AVL树的要求。
（调整操作非常的复杂，这个时候会造成这个数的删除操作变得很低效）

为解决这个问题因此产生了红黑树

红黑树

红黑树的特点：插入查找删除时间复杂度为O(logN)

红黑树是AVL树的进一步改进，让查找，删除能比较均匀（不至于说，插入，删除操作太拉跨）
本质上是一颗放松规则的AVL树：也要求这个二叉搜索树保持平衡，但是没要求那么严格。
这里的规则放松，就可以保证触发调整的情况没那么频繁~（规则本身其实挺复杂的）
虽然查找可能比AVL树稍逊一筹，但是差异不大。同时可以保证插入，删除效率更高。

哈希表

**哈希表的特点：**插入查找删除时间复杂度为O(1)

哈希表的时间复杂度如此高效的原因：主要是借助了数组取下标的“随机访问”能力(取下标非常高效）

• 哈希表这里存在哈希冲突问题
• 挂链表方式
• 往后找一个空位的方式（线性探测/二次探测）

如果索引使用哈希表是否可行？
可行，但是又不可行
可行：确实提高了查找效率
不可行：存在很大的局限性

• 一个哈希表，要想查询，有一个很关键的事，必须比较相等
• 哈希查询的时候，只能查某个key==具体值
• 但是sql中存在很多其它的查询，<,>,=…
• 正因此如此，咱们在使用标准库HashMap的时候，就要求key的类型，必须要提供“比较相等”（equals)这样的方法实现。

N叉搜索树

MySql的索引中最常用的数据结构，其实是一个N叉搜索树！
用N叉的目的就是能够减少高度~
高度低了，此时查找时候比较次数就少了，磁盘IO就少了，效率就提高了

B+树

MySql中的索引，其中最常用的结构，就是B+树
（B+树就是一种特殊的N叉搜索树）

• 为理解B+树，先需要连接B树（有的书叫B-树）

B树也是N叉搜索树
不光是每个节点有多个叉
同时，每个节点，也能保持多个数据

B树的特点：

• N叉搜索树，每个节点可能会包含N个子树
• 每个节点都存在多个值
• 保证类似“二叉搜索树”一样的规则

B+树：

B+树是B树的进一步改进
B+树于B树最明显的区别就是两个方面
1：非叶子节点的值，可能会存在重复。这样就能保证最终的叶子节点这一层，就是完整的数据集合
2：提高类似于链表这样的方式，把所有的叶子节点按照顺序，连接了起来

B+树的优势：

• 1.非常善于进行范围查找
• 2.所有的查询最终都是落在叶子节点上，查询速度是比较稳定的（稳定性其实还是非常给力的特性）
• 3.由于叶子节点是数据的全集，因此就可以把叶子节点存到硬盘上，非叶子节点直接存到内存中。这又进一步大大降低了读取硬盘的次数.

这里的第三点是B+树的大杀器！！！

事务

• 数据库中的事务是指对数据库执行一批操作，这些操作最终要么全部执行成功，要么全部失败。

事务，最核心的特点，就是将一系列操作打包到一起，构成一个整体。
这个整体，要么全部做完，要不一个都不做。不会出现“做了一半，另一半没做的情况”。

事务的四个核心特性：

• 原子性：

把一组操作打包在一起，要么全部做完，要么一个都不做

• 一致性：

执行事务之前，和执行事务之后，当前表里面的数据都是合理的状态~

• 持久性：

事务操作的数据都是直接操作硬盘
硬盘的数据都是持久化存储的（数据只要改了，那么就会一直存在，不会因为重启了就没了）

• 隔离性：

多个事务，并发执行时。
一个事务的执行不能被其他事务干扰。每个事务的执行过程是相对独立的。