前言：

索引简介：

索引结构：

二叉树索引结构

Tree（普通二叉树）

B-Tree(多路平衡查找树)

B+Tree

哈希索引数据结构

总结：

前言：

在实际生活中，我们对SQL语句进行优化实际上有很大一部分都是对索引进行优化，因此对索引有一个较好的掌握度至关重要。而讲索引必定会引用到很多的数据结构，因此我们在这里向大家提供一个网站：数据结构可视化 (usfca.edu)。他会对我们输入的数据逐步生成我们想要演示的数据结构动图。方便各位对各种数据结构有更加深刻的了解。

索引简介：

索引是用于加速数据库中数据检索的一种有序的数据结构。在数据库中，数据存储在表中，表中的每一行称为记录，每一列称为字段。当我们需要检索、查询表中的某些数据时，如果表中数据量很大，那么就会变得非常耗时。这时，使用索引可以快速定位到符合条件的记录，从而提高查询效率。

索引的本质是一个存储有序键值对的数据结构，其中键是表中某一列的值，而值是指向该值所在记录的指针。索引对于某一列的值建立了快速的查找路径，使得查询操作不再需要对整个表中的数据进行扫描，而是直接定位到符合条件的记录。

索引类型：

B树索引
B+树索引
hash索引

当没有索引的时候，如果我们要对一个数据库进行条件查询操作，我们的数据库会对每一条数据都进行查询判断，直到找出来符合条件的数据

B树和B+树

B树和B+树都是一种基于磁盘存储的平衡树，被广泛应用于数据库索引结构中。它们的主要区别在于：

1. B树中既存储数据又存储索引，而B+树只存储索引，数据存储在叶子节点上。

2. B树的每个节点可以存储的关键字数目较小，一般不超过2个。而B+树的每个节点可以存储的关键字数目较多，一般可以存储几十个甚至几百个。

3. B树中的非叶子节点和叶子节点的存储方式不同，而B+树的非叶子节点和叶子节点的存储方式相同。

4. B树采用的是节点分裂和合并方式来维护平衡，而B+树采用的是节点分裂和叶子节点链表方式来维护平衡。

因为B+树节点只存储索引，数据存储在叶子节点上，因此在查询范围查找、顺序查找的情况下，B+树比B树更适合，因为B+树的叶子节点形成了一个链表，可以很快地查找到指定范围内的数据。而对于B树，需要遍历整个树结构才能找到想要的数据，这会导致非常高的时间成本。在数据库索引的应用中，B+树是更常用的一种索引结构。

案例：

例如我们如果要查询年龄大于40岁的员工，此时我们没有建立索引，我们就会逐一遍历这些数据，直至数据完结。（并不是找到一条符合条件的之后就结束查询，而是会遍历完整个表，因为无法确定这条数据之后还是否会有符合条件的数据）。

我们把这种查询方式叫做全表查询。

无索引查询：

索引的优点：

提高数据的查询效率：索引可以加快数据库的查询效率。通过建立索引，可以对关键字进行快速的定位和访问，从而最大限度地减少了磁盘I/O的次数，降低查询数据的时间成本。
减少数据的重复存储：索引存储的是关键字的位置信息，可以避免在表中重复存储关键字，减少数据的存储空间，提高存储效率。
提高数据的完整性和准确性：索引可以对数据进行唯一性、完整性约束，防止数据重复或者无效数据的出现。
优化数据的排序和分组操作：索引可以优化数据的排序和分组操作，使这些操作更快捷和更有效率。
支持高并发查询操作：在高并发的情况下，索引可以提高数据库的查询效率，减少数据库的响应时间，从而提升了系统的性能。

索引的缺点：

增加了存储空间和维护成本：索引需要占用额外的存储空间，并且每次对数据进行更新、插入或删除等操作时都需要更新对应的索引，增加了维护成本。
索引可能不适用于所有查询：不是所有查询都能够使用索引。如果查询中包含了大量的计算、表达式、函数或者是使用了非索引列进行排序和分组，那么索引对于提高查询效率的作用就会较小。
索引可能造成资源竞争和锁的问题：当多个客户端同时访问同一个索引时，就可能会出现资源竞争和锁的问题，降低系统的并发性和性能。
索引可能会降低数据更新、插入和删除的效率：因为每次对数据进行更新、插入或删除等操作时都需要更新对应的索引，所以这些操作的效率可能会降低。

索引结构：

索引结构随着底层的存储引擎不同而会有不同的数据结构。

引擎对索引的支持情况：

我们平时说的索引，如果没有特别指明，都是指B+树结构组织的索引。

二叉树索引结构

Tree（普通二叉树）

在这里我们可以看到：如果二叉树是按照顺序结构插入，那么他就是一个链表，查询性能会大大降低。

而为了解决顺序结构的插入问题，我们引入了红黑树。

而为了解决二叉树在层级较深的时候，会有检索速度慢的问题。我们又想到了一个方法：

既然检索速度慢是因为每个层级只能有两个节点，那我们能否开发出来一种树，而这种树每一个层级拥有多个节点，那么我们不就解决了数据结构多的情况下普通树太多引发的层级过多的问题。

B-Tree(多路平衡查找树)

B-Tree树的生成分裂问题一直都是一个难点，搞不清楚的同学可以去这个网站：B-Tree Visualization (usfca.edu)，自己输入几组数据，它会自动生成从0开始形成树的动图来让各位同学对B-Tree的形成更有体会。

我们以一颗最大度数为5的b-tree为例（每个接待你最多存储4个key，五个指针）

树的度数就是指一个节点的子节点个数：

翻译一下最上级的指针指向：

小于20的指向一个节点
20到30之间的指向一个节点
30到62之间的指向一个节点
62到89之间的指向一个节点
大于89的指向一个节点

这也就是为什么指针的数量总是比数据的数量多一个

B+Tree

B+树节点只存储索引，数据存储在叶子节点上，因此在查询范围查找、顺序查找的情况下，B+树比B树更适合，因为B+树的叶子节点形成了一个链表，可以很快地查找到指定范围内的数据。

B+树的特点：

所有的数据都会出现在叶子节点。
叶子节点形成一个单向链表。

但需要注意的是MySQL索引中并不会直接使用这种原版的B+树，而是做了以下改进：

向叶子节点中的各个节点再次添加一个指针，以此来指向相邻的节点，这种做法优化了在查询数据的时候的遍历问题，优化了时间复杂度。

哈希索引数据结构

哈希索引是一种常见的索引结构，它使用哈希函数将关键字映射到哈希表中的位置，从而实现快速的查找操作。在哈希表中，每个关键字都被分配一个唯一的哈希值，这个哈希值通常是一个整数，它表示该关键字在哈希表中的位置。

当需要查找一个关键字时，哈希函数可以快速计算出它在哈希表中的位置，并且只需要访问一个位置，就可以找到对应的数据。因此，哈希索引具有非常高效的查找性能，速度快且稳定。

但是，哈希索引也有一些局限性。由于哈希函数是不可逆的，无法直接从哈希值中恢复原始数据，所以哈希索引不支持范围查找和排序操作。并且，当多个关键字被映射到同一个哈希值时，哈希表必须使用冲突解决策略来处理这些冲突。常见的冲突解决方法包括链式哈希和开放地址哈希等。

链式哈希（Chaining Hash）和开放地址哈希（Open Addressing Hash）都是常用的哈希表实现方式。

1.链式哈希将哈希冲突的元素放入同一个链表中，每个链表节点包含了关键字和对应的值，链表头节点位于哈希表中的对应槽位中。插入操作只需要先对元素进行哈希计算找到相应的槽位，然后再在对应槽位的链表中进行元素的插入，查找操作只需要先对元素进行哈希计算找到相应的槽位，然后再在对应槽位的链表中进行线性查找即可。

2.开放地址哈希则是在哈希表中找到一个可用的槽位作为元素存放的位置。当遇到冲突时，需要根据哈希表中不同的探查序列方法（例如线性探查、二次探查或双重哈希等），搜索哈希表中下一个可用的槽位，直到找到可用的槽位。这种方法使得哈希表中不需要链表等额外空间来存储冲突的元素，从而节约了空间。

哈希表索引数据结构（链式哈希解决的哈希冲突）

哈希索引特点：

快速查找：哈希索引通过对关键字进行哈希函数运算，将其映射到哈希表中的一个特定位置，从而可以快速的查找到对应的数据。对于大量数据的查询，哈希索引比其他类型的索引更快。
不支持排序和模糊匹配：与其他类型的索引相比，哈希索引重点在于等值查找，不支持通过关键字进行排序或者模糊匹配。因此，在需要排序或者模糊查询的情况下，哈希索引比较无效。
不支持范围查询：哈希索引是用哈希函数将关键字转化为固定的位置索引，因此不支持范围查询。
内存占用较小：哈希索引中不需要存储关键字的排序值，只需要存储关键字哈希值及其对应的指针向量。因此，哈希索引的内存占用较小。
高并发时性能较差：当有大量并发查询时，因为哈希索引使用哈希函数将关键字映射到表中一个位置，不同数据可能被映射到同一个位置，从而导致哈希冲突，因此当前查询可能需要等待前一个查询完成，导致效率降低。