某网站seo策划方案,鞍山在网络做推广,网站界面设计用户体验,北京网站建设石榴汇本章概览 索引的出现就是为了提高数据查询的效率#xff0c;实际上可以提高读写效率的数据节后有很多
索引常见模型
哈希表是一种以键 - 值#xff08;key-value#xff09;存储数据的结构#xff0c;用哈希函数把key计算成一个值#xff0c;这个值代表一个位置#xf…本章概览 索引的出现就是为了提高数据查询的效率实际上可以提高读写效率的数据节后有很多
索引常见模型
哈希表是一种以键 - 值key-value存储数据的结构用哈希函数把key计算成一个值这个值代表一个位置可能会出现不同key计算出位置相同这是再拉出一个链表。这种结构等值查询和插入的效率都很快但是不是按顺序插入的使用区间查询的时候就需要全部扫描一遍了。 所以哈希表这种结构适用于只有等值查询的场景比如 Memcached 及其他一些 NoSQL 引擎。
有序数组在等值查询和范围查询场景中性能都很优秀时间复杂度在O(log(N))但是更新数据的时候需要数据搬移所以有序数组索引只适用于静态存储引擎比如你要保存的是 2017 年某个城市的所有人口信息这类不会再修改的数据。
二叉搜索树的特点是父节点左子树所有结点的值小于父节点的值右子树所有结点的值大于父节点的值这个时间复杂度是 O(log(N))。 数可以有二叉也可有多叉二叉树的查询效率最高实际上数据库存储不用二叉树原因在于索引不仅存在内存也在磁盘上寻址需要时间层数高意味着磁盘数据块多查询随机读取数据块耗时多。
以 InnoDB 的一个整数字段索引为例这个 N 差不多是 1200。这棵树高是 4 的时候就可以存 1200 的 3 次方个值这已经 17 亿了。考虑到树根的数据块总是在内存中的一个 10 亿行的表上一个整数字段的索引查找一个值最多只需要访问 3 次磁盘。其实树的第二层也有很大概率在内存中那么访问磁盘的平均次数就更少了。 innodb最小存储单元是数据页16k整型bigint大小是8byte 指向子树的pointer是6byte,1600/14约等于1170。 这样可以减少随机访问读取数据块
Innodb的索引模型
在innodb位存储引擎的mysql中每张表就是多个B树每一个索引在 InnoDB 里面对应一棵 B 树。执行查询的效率主键索引非主键索引不使用索引不适应索引查询则从B数的叶子节点遍历
mysql create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engineInnoDB;表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)两棵树的示例示意图如下。 主键索引的叶子节点存的是整行数据。在 InnoDB 里主键索引也被称为聚簇索引clustered index。 非主键索引的叶子节点内容是主键的值。在 InnoDB 里非主键索引也被称为二级索引secondary index。
基于主键索引和普通索引的查询有什么区别 主键索引叶子节点是整行数据非主键索引叶子节点是主键ID如果需要查询整行数据需要根据这个ID再去主键索引树查询一次这个过程叫回表。
索引维护
B 树为了维护索引有序性在插入新值的时候需要做必要的维护。以上面这个图为例如果插入新的行 ID 值为 700则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400就相对麻烦了需要逻辑上挪动后面的数据空出位置。
而更糟的情况是如果 R5 所在的数据页已经满了根据 B 树的算法这时候需要申请一个新的数据页然后挪动部分数据过去。这个过程称为页分裂。在这种情况下性能自然会受影响。
当然有分裂就有合并。当相邻两个页由于删除了数据利用率很低之后会将数据页做合并。合并的过程可以认为是分裂过程的逆过程。
除了考虑性能外我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段比如字符串类型的身份证号那应该用身份证号做主键还是用自增字段做主键呢 由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键那么每个二级索引的叶子节点占用约 20 个字节而如果用整型做主键则只要 4 个字节如果是长整型bigint则是 8 个字节。
显然主键长度越小普通索引的叶子节点就越小普通索引占用的空间也就越小。
