mysql用的什么数据结构

咱们聊聊MySQL的数据结构和索引，这俩可是数据库性能的“秘密武器”。
首先，MySQL用行和列来构建数据的基本框架，就像表格里的格子，每个格子都有它的小秘密。
行代表一条条完整的信息，而列则是信息的属性，比如名字啦、年龄啦这些。

然后，MySQL还玩儿出了花，它不是简单地堆砌数据，而是通过各种索引来提升查找效率。
比如，B+树索引就特别适合做范围查询和排序，它就像一棵树，把数据按顺序排好，让你能更快地找到你想要的。

说到索引，还得提提InnoDB存储引擎。
它默认用的就是B+树索引，这玩意儿平衡又有序，查询效率杠杠的。
还有其他类型的索引，像散列索引适合快速匹配，位图索引在处理少量数据时特别高效，全文索引则是文本搜索的好帮手。

这些索引之间还互相配合，比如主键索引让查询更快，二级索引则需要多一步查找，而覆盖索引则能直接从索引里找到所有你需要的数据，省去了回表查询的麻烦。

为什么这些结构这么受欢迎呢？主要是因为B+树索引那种平衡、有序、高扇出的特性特别适合磁盘存储，能减少读取数据的次数。
而且，根据不同的查询需求选择合适的索引，能显著提升数据库的整体性能。

总之，MySQL就是通过这种行列结构和各种索引的巧妙结合，既保证了数据的事务安全，又优化了读写性能，让数据库工作得既快又稳。

mysql 索引有哪些？各⽤用了了哪些数据结构

聊聊数据库索引的那些事儿，从数据结构的角度来看主要有这么几种：
首先是B+树索引，这个的时间复杂度是O(log(n))。
如果你想深入了解的话，可以看看《MySQL索引背后的数据结构及算法原理》这篇文章，写得挺详细的。

然后是hash索引。
这种索引有个特点，就是只能用来做"="、"IN"和"<=>"这样的查询，搞不了范围查询。
不过它的查询效率是真高，因为索引检索可以直接定位，不像B+树那样要从根节点到枝节点，最后才到页节点，得多费点IO。
所以，hash索引的查询速度要比B+树索引快不少。
不过，hash索引只有Memory存储引擎才支持。

FULLTEXT索引也是个不错的选择，现在MyISAM和InnoDB引擎都支持了。

最后是R-Tree索引，这个主要用于对GIS数据类型创建SPATIAL索引的。

MySQL索引的底层数据结构原理剖析(二叉树、 红黑树、Hash、B-Tree、B+Tree)

在MySQL的5 .7 和8 .0版本中，默认的索引类型是B+Tree，当然也有Hash索引可选。
对于更早的版本，这里就不详细展开了。
如果你对数据结构感兴趣，可以看看这个网站：cs.usfca.edu/~galles/visualization/Algorithms.，上面有很多图解，挺直观的。

想象一下，左边是一个没有索引的表格，右边是一个以col2 为索引列的二叉树索引。
这两张图对比得挺明显，有索引和没索引的区别有多大。
就拿这个SQL语句select from t where col2 =8 9 来说吧。

如果没有索引，那得从上往下一个个查找，可能得6 次才能找到，这意味着要经历6 次磁盘IO操作。
但如果有二叉树索引，可能只需要2 次查找就能定位到，也就是2 次磁盘IO，你看，性能提升是不是很显著？
二叉树的好处在于，它的左子节点值总是小于节点值，右子节点值总是大于节点值。
当数据量很大，而且要找的数据又靠后时，和没有索引比起来，二叉树的查询优势就特别明显。
不过，如果二叉树出现单边增长，那它就变成了一个链，这样查找速度的优势就没了。

红黑树虽然比二叉树好一些，能缓解单边过长的问题，但它还是有高度的问题。
假设有1 00万条数据，红黑树的高度大约是2 的2 0次方，也就是说，可能得2 0次磁盘IO才能找到数据，这样性能就会受影响。
所以红黑树也不是最佳选择。

实际上，我们设想的那种每个节点存多个索引+磁盘地址的结构，就是B-Tree。
B-Tree是一种平衡的多路查找树，它在文件系统和数据库系统中都有应用，主要用作文件的索引。
B-Tree的特点是节点中的key和指针是互相间隔的，叶子节点具有相同的深度，而且节点中的数据索引是从左往右递增排列的。

B+Tree是B-Tree的一种优化，它更适合实现外存储索引结构。
在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大增加每个节点存储的key值数量，降低B+Tree的高度。

聚集索引也就是主键索引，它的叶子节点中存储的是该主键对应的一整行数据。
非聚集索引，也就是辅助索引，它的叶子节点中存储的是该索引对应的那行数据的主键值。
非聚集索引的寻址过程有两种情况：如果非聚集索引已经索引覆盖了，那么只需要遍历这非聚集索引这一个B+Tree即可；如果不能索引覆盖，那么先需要在非聚集索引这个B+Tree上两次IO找到该行数据对应的主键值，然后拿着主键去聚集索引的B+Tree上找对应的其它数据。

InnoDB表必须有主键，而且推荐使用整型的自增主键。
这是因为后面的主键索引总是大于前面的主键索引，这样在做范围查询时，非常方便找到需要的数据。
而且，自增的主键每次添加都是在后面插入，树分裂的机会小；而UUID大小不确定，分裂机会大，需要重新平衡树结构，性能损耗大。

非主键索引的叶子节点存储的是主键值，而不是全部数据，这是因为节省空间。
如果每个非主键索引都存储一份完整的数据，那会非常占用空间。
而且，如果修改了索引1 5 的数据，只要修改主键的data即可，而如果非主键的data也存一份的话，那得修改两份，这样就涉及到事务一致性的问题，耗时，性能低。

我们希望使用覆盖索引，是因为如果非聚集索引中能索引覆盖，那么我们只需要遍历非聚集索引这个B+Tree从其中的Key里拿到索引值就可，只需要遍历一棵树。
如果不能索引覆盖，需要先遍历非聚集索引，然后拿到data中存储的主键值，再去聚集索引中遍历查找数据，相比索引覆盖的话，IO次数更多，性能相对低。

MyISAM和InnoDB的索引结构也有区别。
在MyISAM下，索引结构文件是分开的，存储引擎在磁盘中文件有三个，分别是数据表定义文件、索引文件、数据文件。
而InnoDB存储引擎它的表数据文件本身就是按B+Tree组织的一个索引文件。
一个frm文件存储数据表定义，一个ibd文件存放的索引和实际数据。
InnoDB在查找数据时，性能比MyISAM高。

嵌入式面试常问的数据结构（三）

在嵌入式系统面试中，除了那些老生常谈的链表、栈、队列，B+树和跳表这两种高级数据结构也经常被拿出来溜。
它们在数据库索引、缓存系统等领域可是相当有分量。
下面就给大家好好扒一扒B+树和跳表，顺便说说MySQL为啥不选跳表，而选B+树当索引。

先说说B+树和跳表相同的地方。
最底下那层都装着所有数据，而且是排好序的，这样范围查询起来就特别方便。
另外，上面那些层都是为了提升搜索速度，通过多层索引来加速查找。

那它们俩的区别呢？首先看新增数据。
在B+树里，新增数据要考虑树的平衡，得插到合适的位置，还可能引发节点分裂和重新平衡。
而跳表新增数据时，底层链表插完数据后，往上几层加不加索引就靠随机函数了。
理论上说，为了达到二分查找的效果，每层节点数要是下一层的二分之一。
所以新数据插入时，有5 0%的概率在第二层加索引，2 5 %的概率在第三层，以此类推，直到最顶层。

再来看层数变化。
B+树的层数受插入删除操作和数据平衡影响，而跳表的层数变化完全看随机函数，跟前后上下节点没半毛钱关系。

那么问题来了，MySQL为啥不选跳表，而选B+树当索引呢？主要原因有几点。
B+树是多叉树结构，每个节点都是一个1 6 k的数据页，能存不少索引信息，扇出很高。
这意味着查询数据时，如果数据页都在磁盘里，最多也就查询几次磁盘IO就能找到目标数据。
而跳表是链表结构，一条数据一个节点。
如果底层要存大量数据，还要求每次查询都能达到二分查找的效果，那跳表的高度就会相对比较高，比如2 4 层左右。
最坏情况下，这2 4 层数据还可能分散在不同的数据页里，导致查一次数据要经历多次磁盘IO。

所以说，B+树的高度比跳表低，存同样量级的数据时，查询所需的磁盘IO次数更少，查询速度自然更快。
这也是MySQL为啥选B+树而不是跳表的原因。
对于需要高效处理大量数据的数据库系统来说，这可是非常重要的一点。

总而言之，在嵌入式系统面试中，搞懂B+树和跳表的特点、应用场景，以及它们和数据库索引的关系，对提升咱们的专业素养和竞争力可是很有帮助的。