mysql索引及数据结构

关于mysql索引及数据结构的思维导图，主要内容有数据结构、什么是索引?、存储引擎、为什么建议innodb表必须建主键，且推荐使用整型的自增主键?等。

Mysql

• 索引及数据结构
  • 数据结构
    • 二叉树
      • 数据如果是自增的，那么二叉树就变成了一条单向的链表，不能提现索引的优点，查找速度并不快速了，这是二叉树的一个缺点
    • 红黑树（平衡二叉树）
      • 对二叉树做了平衡，但数据量大的话会导致树的高度太高，导致查询效率低
    • B-tree
      • 1.叶节点具有相同的深度，叶节点无指针 2.所有索引元素不重复 3.数据索引从做到右递增排序 4.索引下直接放存储地址
    • B+tree
      • B+tree是B-tree的一个变种，叶子节点存储了相邻节点的磁盘地址，双向指针，对于范围查找速度更快，每次从根节点进行查找，页节点分配的空间大小一般是16k，Show global status like ‘innodb_page_size’;执行该sql可以查看页空间大小，指针是下个叶子节点的地址，一个指针大小约占6b，一个bigint类型的字节占8b，那么一页16kb大约能放16kb*1024/(6+8)=1170个元素，三层大约能放千万级别数据量，根节点可能放在内存里面，其他节点放磁盘中，影响查找速度的指标树的高低，mysql最终选择使用B+tree是因为叶子节点不存在数据，从而每页存放的索引更多，减少了树的高度，加大了查找的速度，而B-Tree叶子节点和非叶子节点都存放数据，导致每页能够存放的索引很少，从而导致树的高度变大，增加了查找的次数，使查询速度变慢，同时B+tree的非叶子节点之间存在双向指针，因此mysql最终选择了B+tree来作为索引的数据结构；存储引擎是表级别的。
    • Hash
      • 1.Hash对索引的key进行一次hash计算就可以定位到数据存储的位置 2.仅能满足“=”，“in”，不支持范围查询 3.Hash冲突问题可能导致查询速度变慢
  • 什么是索引？
    • 索引是获取数据的排好序的数据结构
  • 存储引擎
    • innodb
      • Innodb一张表只存在一个聚集索引，而二级索引的叶子节点索引存放的是主键索引的rowId， 一张表每增加一个索引就会多一个索引的树状结构 tablename.frm tablename.ibd 索引和数据在一个文件中
    • mysiam
      • Mysiam存储引擎表包含三个文件， tablename.frm：表结构文件 tablename.myd：表数据文件 tablename.myi：表索引文件 Mysiam存储引擎也是非聚簇索引，索引下存放的是该数据的地址，拿到该地址去tablename.myd文件中查找数据，但mysiam的数据结构也是B+tree，将数据根据主键排好序，只是索引位置存放的是地址，而Innodb存储引擎存放的是数据，Innodb存储引擎是聚簇簇索引，Innodb存储引擎表包含两个文件， tablename.frm：表结构文件 tablename.ibd：索引和数据文件
  • 为什么建议innodb表必须建主键，且推荐使用整型的自增主键？
    • 如果一张innodb表中存在主键，那么会根据主键去建索引，如果表无主键也无索引，那么mysql会从所有列中选择一列所有数据都不相同的一列去建索引结构，如果没有选择到，那mysql会自己建一个隐藏列作为主键唯一id（类似rowId），并根据这个隐藏主键来建索引结构即根据隐藏主键的id来组织整张表的数据；mysql的资源是很宝贵的，能自己主动来做的可以自己做，建表的时候添加主键，mysql会根据指定的主键来组织整张表的数据，而不会自己去创建一个隐藏列来维护数据，减轻mysql自身的工作。 为什么建议使用整型的自增主键？ 1.如果是整型的只比较一次，比如3>2，而uuid或者string类型，则会逐个比较字符，显然速度很慢。 2.主键字段大小越小，每个叶子节点存放的索引就越大，占用的磁盘空间也就相对较少，生产环境的磁盘性能很高，但也很贵，可以节省磁盘空间； 3.如果不是自增，会导致树的分裂、树的平衡发生，而自增会一直往后插入分节点，而不是分裂和平衡节点，这样自增的主键效率会更高一些。 Innodb一张表只存在一个聚集索引，而二级索引的叶子节点索引存放的是主键索引的rowId， 一张表每增加一个索引就会多一个索引的树状结构。
  • innodb表非主键索引结构叶子节点存储的是主键值？
    • 为了一致性、为了节省空间
  • 索引最左前缀原理
    • 新建一个索引或联合索引，数据会根据索引字段把整张表的数据排好序，会根据联合索引的顺序，从左到右进行比对，根据ASCII码表将第一个字段大小比较，哪个大就放后面，如果相等，再比较第二个字段，哪个大就确定了位置，依次循环比较大小，就这样把整张表的数据按顺序排好序，所以查找的时候要根据这个排序的原则进行，不然就会导致索引失效，这也就是所谓的最左前缀原则的由来。