数据结构网站(mysql索引底层数据结构和算法)

分析以下几条 sql 根据索引使用情况1. SELECT * FROM titles WHERE emp_no='10001' AND title='Senior Engineer' ANDfrom_date='1986-06-26';2. SELECT * FROM titles WHERE title='Senior Engineer' ;3. SELECT * FROM titles WHERE emp_no > ‘10001';4. SELECT * FROM titles WHERE emp_no > ‘10001' and title='Senior Engineer';5. SELECT * FROM titles WHERE emp_no > ‘10001' order BY title;索引到底是什么索引是帮助 MySQL 高效获取数据的排好序的数据结构;索引存储在文件里;索引结构;二叉:一个节点的左键点小于该节点,右节点大于该节点,但是如果插入二叉树的数据是有序的,就会形成二叉树的极端情况,形成链表,我们知道树的查询复杂度跟树的高度有关,树越高,那么查询事件复杂度就越高,并且需要更多的磁盘IO,所以需要通过某种约束来保证树的平衡,所以MySQL不用二叉存储索引;二叉结构存储数据的示意图:红黑树:那么红黑树就是平衡二叉树中的一种,它通过一系列的规则来保证树的平衡。但是在大规模数据存储的时候,红黑树常常会因为树的深度过高而导致磁盘IO读写过于频繁,导致效率底下,为什么会形成这种情况呢,我们知道要获取磁盘上的数据,必须通过磁盘移动臂移动到数据所在的柱面,然后找到指定盘面,接着旋转盘面找到数据所在的磁道,最后进行读写,这种涉及到物理操作情况下,性能自然会很低下。MySQL不用红黑树存储索引;红黑树存储的数据示意图:HASH:如果不是范围查找用hash效率也是很高的,hash索引查询单条确实比较快,但是他是无序的,查询多条或者排序的话性能就比较低了;BTREE:B树也就是B-树,B树是一个多路搜索树,也就是每个节点可以有多个子节点,这样是为了降低树的高度,减少磁盘IO次数;B+树是B树的优化,他的子节点只存储键而不存储数据,数据全部存在叶子节点,并且叶子节点间通过指针进行连接,这样因为子节点不存储数据,那么磁盘可以一次读取更多的子节点,减少IO次数,并且叶子节点想通,如果想查询10-100的数据只需要找到头尾就可以了。B-Trees示意图:B+Trees示意图:数据结构网站:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html到此为止,我们知道了Mysql为什么使用B+树了,因为我们平常的业务查询一般可能不是查询一条,而是查询多条,hash索引查询单条确实比较快,但是他是无序的,查询多条或者排序的话性能就比较低了,并且在内存资源紧张的情况下,树索引可以分批装入内存进行计算。红黑树因为大数据存储下,树的高度很高,这样可能会导致多次IO,查询效率比较低。而B+树可以一次性装入更多的叶子节点到内存,并且树的高度可以控制到很低,叶子节点存储数据并且形成链表可以避免跨层查询。索引概述磁盘存取原理(一般使用磁盘I/O次数评价索引结构的优劣,一次磁盘io指指令一般是通知磁盘开始扇区位置,然后给出需要从这个初始扇区往后读取的连续扇区个数,所以树的层级越深磁盘io读取越频繁)寻道时间 ( 速度慢,费时 )旋转时间 ( 速度较快 )不同面上的磁道编号则组成了一个圆柱面磁盘IO为什么慢先温习下知识点:磁盘IO时间 = 寻道 + 磁盘旋转 + 数据传输时间从磁盘读取数据时,系统会将逻辑地址发给磁盘,磁盘将逻辑地址转换为物理地址(哪个磁道,哪个扇区)。 磁头进行机械运动,先找到相应磁道,再找该磁道的对应扇区,扇区是磁盘的最小存储单元(见图1-1)。 图1-1 磁盘物理结构当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。索引底层数据结构与算法主键索引和辅助索引的区别?逐渐索引:逐渐索引当做分叶子节点的值,行的记录被放到叶子节点上,索引和数据放到一起了。辅助索引:辅助索引的value是主键索引的key,辅助索引通过b+tree找到主键索引,然后通过主键索引找到对应的行的记录;为啥InnoDB必须有主键,并且推荐使用整型的自增主键?1、如果设置了主键,那么InnoDB会选择主键作为聚集索引、如果没有显式定义主键,则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引、如果也没有这样的唯一索引,则InnoDB会选择内置6字节长的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增)。2、如果表使用自增主键那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,主键的顺序按照数据记录的插入顺序排列,自动有序。当一页写满,就会自动开辟一个新的页,充分利用空间;3、如果使用非自增主键(如果身份证号或学号或者uuid等)由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页的中间某个位置,此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。字符串长查询效率低,浪费空间,增加磁盘io联合索引结构索引最左前缀原理?按照最左前缀原理只有第三个sql走索引了EXPLAIN SELECT * FROM employees WHERE NAME = 'LiLei' AND age = 22 AND POSITION ='manager';EXPLAIN SELECT * FROM employees WHERE NAME = 'LiLei' AND POSITION ='manager' AND age = 22 ;这两个都用到索引了,如果索引列都用到mysql会自动排序索引的EXPLAIN SELECT * FROM employees WHERE NAME = 'LiLei' AND POSITION ='manager' AND age > 22 ;这个是用到索引的有没有走索引的依据是type类型在all之前依次从最优到最差分别为:system > const > eq_ref > ref > range > index > ALL一般来说,得保证查询达到range级别,最好达到ref


本文出自快速备案,转载时请注明出处及相应链接。

本文永久链接: https://www.xiaosb.com/beian/45791/