一、数据结构

数据结构大致可以分为两种 —— 线性结构 和 非线性结构。

1. 线性结构

线性结构是数据结构中的一种基本结构，它的特点是数据元素之间存在一对一的前后关系。线性结构中的数据元素排列成一个线性序列，可以用顺序存储或链式存储来实现。

常见的线性结构有以下几种：

1. 数组：连续存储的一组相同类型的元素，可以通过索引直接访问。

2. 链表：由节点组成的集合，每个节点包含数据和指向下一个节点的指针。

3. 栈：具有先进后出（LIFO）特性的线性表，只能在栈顶进行插入和删除操作。

4. 队列：具有先进先出（FIFO）特性的线性表，只能在队尾插入，在队头删除。

5. 哈希表：使用哈希函数将键映射到存储位置，并通过解决冲突处理碰撞问题。

2. 非线性结构

非线性结构是数据结构中的另一种类型，与线性结构不同，它的数据元素之间并不是简单的前后关系。

常见的非线性结构有以下几种：

1. 树：由节点和边组成的层次结构，每个节点可以有多个子节点。

2. 图：由节点和边组成的集合，节点之间可以存在多种关系，如有向图和无向图。

3. 堆：一种特殊的树形结构，通常用于实现优先队列，具有父节点小于（或大于）子节点的特性。

4. 散列表：基于哈希函数将键映射到存储位置，并通过解决冲突处理碰撞问题。

5. 图表：由多个表格连接而成，用于表示复杂的关系和数据依赖。

还有例如跳表之类的其他的数据结构，也都是从基础数据结构演化出来的，用来解决指定的场景问题。

二、索引的数据结构

我们先把记忆中的 Mysql的索引是使用B+树做的，因为B+树有 xxx 的优点 抹去，没有人在开发的时候就能直接想到完美的解决方案，所以我们也来推导一下索引的数据结构。

1. 索引的作用

索引是用来做什么的？

索引在数据库和数据结构中起到了重要的作用，它能够提高数据的查询效率和访问速度。以下是索引的几个主要作用：

1. 加快数据检索：索引可以按照特定的规则对数据进行排序和组织，从而加快数据的查找速度。通过使用合适的索引，可以避免全表扫描，减少查询所需的时间复杂度。

2. 提高查询性能：当数据库中有大量记录时，使用索引可以显著提升查询性能。索引将数据按照特定列进行排序和分组，使得数据库系统只需搜索一部分数据而不是全部数据。

3. 优化排序和分组操作：索引可以帮助数据库系统快速地进行排序和分组操作。如果在执行SQL语句时需要对结果进行排序或者分组，使用合适的索引可以节省大量计算时间。

4. 约束唯一性：通过在某些字段上创建唯一索引，可以保证该字段值的唯一性，防止重复插入相同值的情况发生。

5. 改善连接操作：当多个表之间需要进行连接操作时，在关联列上创建合适的索引能够极大地提高连接操作的效率。

尽管索引能够提高查询效率，但也会增加存储空间和更新数据的成本。

索引存储在哪里？

索引存储在数据库管理系统的内存和磁盘中。具体来说，有以下几种常见的索引存储方式：

1. 内存中的索引：为了提高查询效率，数据库管理系统通常会将常用的索引数据加载到内存中进行操作。这样可以避免频繁的磁盘访问，加快查询速度。

2. 磁盘上的索引：当内存无法容纳全部索引数据时，数据库管理系统会将部分或全部索引数据存储在磁盘上。通常使用B+树等数据结构来组织和管理索引数据，以支持高效地查找、插入和删除操作。

3. 辅助文件：一些数据库系统会将较大或者不常用的索引存储在单独的文件中，而不是放在主要的数据文件中。这样可以降低主要数据文件的大小，减少IO开销，并且更灵活地管理索引。

我们都说数据持久化数据持久化，其实就是把内存里的数据转移到硬盘上，这样即便是设备断电了，数据也不会受到影响。但是有利必有弊，数据存储在硬盘上带来的后果就是读取的速度变慢。又是变慢，能变多慢呢？内存是纳秒级的处理速度，硬盘是毫秒级的处理速度，二者相差百万倍，这就是速度的差异。所以我们实际使用索引的时候，会把索引从硬盘中读到内存里，然后通过内存里的索引，从硬盘中找到数据。

但是这样优化了又如何呢，只要需要读硬盘，那就会消耗时间，硬盘IO越多，时间消耗越多。

除此之外，我们使用索引不只是为了能够迅速找到某一个数据，而是能够迅速找到某一个范围区间的数据，能够动态的执行有关数据的操作。

那么在上述的描述下，索引能够使用的数据结构就有这么几个 —— 哈希表、跳表、树。

2. 哈希表

哈希表：也叫做散列表。是根据关键字和值（Key-Value）直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value，然后把键值对映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（散列函数），用于存放记录的数组叫做 哈希表（散列表）。哈希表的关键思想是使用哈希函数，将键 key 和值 value 映射到对应表的某个区块中。可以将算法思想分为两个部分：

• 向哈希表中插入一个关键字：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中

• 在哈希表中搜索一个关键字：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值

哈希表的原理示例图如下所示：

哈希表的精确查询时间复杂度是 O(1) ，为什么呢？因为计算目标 key 的 hash 值，然后直接对应到数组的下标，这个过程大大的减少了查询所需要的时间。在产生了 hash 碰撞的时候，也会使用链表和红黑树的方式加快碰撞情况下，查询目标值的速度。

这样的话，我们索引的数据结构完全可以采用哈希表的形式来做，效率非常高。但是为什么不这么做呢？

如果使用哈希表来当作索引的数据结构，在进行范围查询的时候需要全部扫描，这是一笔不菲的代价。

3. 跳表

跳表（Skip List）是一种用于实现有序数据结构的数据结构，它在链表的基础上通过添加多级索引来加速搜索操作。

跳表由William Pugh在1989年提出，其设计灵感来自于平衡二叉树。相比于传统的链表，在查找元素时，跳表可以通过使用多级索引进行快速定位，并且具备较高的插入和删除效率。

跳表中的每个节点包含一个值和若干个指向下一层节点的指针。最底层是原始链表，每个节点按照值从小到大排列；而上方的各级索引则以不同步长稀疏地链接部分节点。这样，在搜索时可以先沿着最顶层索引开始查找，逐渐向下层细化范围，直到找到目标节点或者确定目标不存在。

跳表的时间复杂度为 O(log n)，其中 n 是元素数量。它相对简单、易于实现，并且支持高效的插入、删除和搜索操作。因此，在某些场景下，跳表可以作为替代平衡二叉树等数据结构的选择。

如图所示，跳表就是在链表的基础上加了索引层，这样就能够实现区间查询的效果。比如我们要查找key = 5，那就先遍历索引层，遍历到3，然后发现下一个索引是6，那么直接从索引层的3往下进入链表，在往后走2步就到key = 5了。

如果数据量非常非常大呢？（图方便这里用 excel 绘制，美观上会差一些）

这样是不是就能发现跳表的好处了，用多个索引划分链表，从高级索引定位到更低级的索引，直到定位到链表中。效率看起来也很高。

但是这还是存在一个问题，我读取完三级索引到内存，然后我还要硬盘IO去读取二级索引，然后还要读取一级索引。还是在硬盘的IO上费了太多的操作。跳表的数据越多，索引层越高，读取索引带来的硬盘IO次数越多，性能降低，这又违背了一开始使用索引的理念。

4. 树

树结构的特性决定了遍历数据本身就支持按区间查询。再加上树是非线性结构的优势相比于线性结构的数组，不必像数组的数据是连续存放的。那么当树结构在插入新数据时就不用像数组插入数据前时，需要将数据所在往后的所有数据节点都得往后挪动的开销。所以树结构更适合插入更新等动态操作的数据结构。

需要C/C++ Linux服务器架构师学习资料加qun579733396获取（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享

三、树

实现索引使用的数据结构看来是要使用树结构了，常用的树都有哪些呢？二叉树、二叉查找树、平衡二叉查找树、红黑树、B树。

二叉树

二叉树是n（n>=0）个结点的有限集合。当n=0时为空树，当n不为0时，二叉树有以下特点：1.每个结点的度不超过2（可以理解为二孩政策下的结点最多只能有两个孩子）；

每个结点的左子树和右子树顺序不能颠倒，所以二叉树是有序树。

特殊二叉树

1. 满二叉树：每一层结点数都达到最大，那么它就是满二叉树。如第1层最多有2 ^0个结点，第2层最多有 2 ^1个结点，则第k层最多有2 ^(k-1)个结点，假设这棵满二叉树有k层，那么它总共有2 ^0+2 ^1+……+2 ^(k-1) = 2 ^k-1个结点。

2. 完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。（简介版：完全二叉树的前k-1层是满二叉树，最后一层从左到右依次连续）

二叉查找树

二叉查找树可以理解为融合了二分查找的二叉树。二分查找大家都熟悉吧，时间复杂度 O(logN) ，比直接遍历的线性查找快的多，但是需要数组是有序的。

所以说，二叉查找树不同于普通的二叉树，二叉查找树是将小于根节点的元素放在左子树，将大于根节点的元素放在右子树。其实就是从某种含义了实现了二分查找的先决条件 —— 数值有序。

但是二叉树是存在弊端的，如果我们每次都插入一个更小的数或者更大的数，那么二叉树就会在一个方向上无限延长，退化成了链表。那链表的时间复杂度是 O(N)，而且又加大了硬盘的IO操作。所以这种结构还是不太行。

平衡二叉查找树

面说一直放更小或者更大的数，让他不断延长，变成一个极端的“很高很瘦”的数，那么用平衡二叉查找树就能解决这个问题。

平衡二叉查找树的关键是 平衡 ，指的是每个节点的左右子树高度差不能超过 1。这样左右子树都能平衡，时间复杂度为 O(logN) 。

无论是二叉树还是二叉查找树还是平衡二叉查找树还是红黑树，他最终都存在一个问题 —— 每个节点只能有 2 个子树。这意味着只要数据量足够大，它总会变成一个深度非常大的树。深度越大，硬盘IO次数越多，性能效率越低，这又双叒叕与索引的初衷背道而驰。

红黑树

与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看，红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一，且节点颜色的划分需要满足特定的规则。

与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转。总的来说，红黑树的统计性能高于AVL。

因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。

对于数据在内存中的情况（如上述的TreeMap和HashMap），红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树并不擅长，因为红黑树长得还是太高了。当数据在磁盘中时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会严重影响性能。

B树

新的数据结构的产生肯定是为了解决之前繁琐的问题。在树的深度不断变大的情况下，B树就应运而生了。

B树的出现解决了树高度的问题，从名字上也能看出来，它不叫B二叉树而是直接叫B树，因为它摆脱了二叉这个概念。它不再限制一个父节点中只能有两个子节点，而是允许拥有 M 个子节点（M > 2）。不仅如此，B树的一个节点可以存储多个元素，相比较于前面的那些二叉树数据结构又将整体的树高度降低了。那么B树实际上就是多叉树。

图中每一个节点叫做 页，是Mysql数据读取的基本单位，也就是上面的磁盘块。其中的 P 是指向子节点的指针。

当数据量足够大的时候，使用平衡二叉查找树则会不断纵向扩展子节点，让整个树变得更高。而B树可以横向扩展子节点，变得更胖，但是树的高度不高，硬盘IO的次数更少。

综上所述，B树已经非常适合用来给Mysql做索引的数据结构了。那么为什么还要去使用B+树呢？实际上B树存在一个缺点，虽然B树实现了区间查找，但是B树的去检查找是基于中序遍历来做的，中序遍历的算法题大家应该都做过，需要来回切换父子节点，切换父子节点在这里就意味着硬盘不断的IO操作，这显然也是不好的。

B+树

B+树其实就是B树的升级版。MySQL 中innoDB引擎中的索引底层数据结构采用的正是B+树。

B+树相对于树做了这些方面的改动：B+树中的非叶子节点只作为索引，不存储数据。转而由叶子节点存放整棵树的所有数据。叶子节点之间再构成一个从小到大的有序的链表并互相指向相邻的叶子节点，也就是在叶子节点之间形成了有序的双向链表。

画图画的不是很清楚，忘记展示双向链表的特点，最下面的箭头指的是相邻的两个叶子是双向的，所有的叶子节点构成双向链表。

再来看B+树的插入和删除，B+树做了大量冗余节点，从上面可以发现父节点的所有元素都会在子节点中出现，这样当删除一个节点时，可以直接从叶子节点中删除，这样效率更快。

相邻的两个叶子是双向的，所有的叶子节点构成双向链表。

再来看B+树的插入和删除，B+树做了大量冗余节点，从上面可以发现父节点的所有元素都会在子节点中出现，这样当删除一个节点时，可以直接从叶子节点中删除，这样效率更快。

B树相比于B+树，B树没有冗余节点，删除节点时会发生复杂的树变形，而B+树有冗余节点，不会涉及到复杂的树变形。而且B+树的插入也是如此，最多只涉及树的一条分支路径。B+树也不用更多复杂算法，可以类似红黑树的旋转去自动平衡。

总结：

mysql选择B+树的原因在于其独特的优势：

1. 良好的平衡性：B+树是一种自平衡的树结构，不论是在插入、删除还是查询操作中，它都能保持相对较好的平衡状态。这使得B+树能够快速定位到目标数据，提高查询效率。

2. 顺序访问性：B+树的所有叶子节点是按照索引键的顺序排序的。这使得范围查询和顺序访问非常高效，因为相邻的数据通常在物理上也是相邻存储的，可以利用磁盘预读提高IO效率。

3. 存储效率：B+树在内存中的节点大小通常比其他树结构更大，这样可以减少磁盘I/O操作的次数。同时，B+树的非叶子节点只存储索引列的值，而不包含实际数据，这进一步减小了索引的尺寸。

4. 支持高并发：B+树的特性使得它能够支持高并发的读写操作。通过使用合适的锁或事务隔离级别，多个并发查询和更新操作可以同时进行而不会出现严重的阻塞或冲突。

5. 易于扩展和维护：B+树的结构相对简单，可以较容易地进行扩展和维护。当插入或删除数据时，B+树只需要调整路径上的少数节点，而不需要整颗树的重构。这样能够有效降低维护成本，并保证索引的高性能。