Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

04 | 深入浅出索引(上) #9

Open
git-zjx opened this issue Jul 18, 2019 · 7 comments
Open

04 | 深入浅出索引(上) #9

git-zjx opened this issue Jul 18, 2019 · 7 comments
Assignees
Projects

Comments

@git-zjx
Copy link
Owner

@git-zjx git-zjx commented Jul 18, 2019

索引的出现主要为了提高数据库的查询效率,像书的目录一样, 是空间换时间的思想

索引的常见数据结构

  • 哈希表

哈希表是一种以键-值(key-value)存储的数据结构,会有一个哈希函数将 key 换算出一个位置,然后将 value 存储进去。如果出现哈希一致的情况,就会拉一个链表出来存储

哈希表适合等值查询的情况

  • 有序数组

有序数组是一种特殊的数组,里面的元素,按一定的顺序排列

有序数据的等值查询和范围查询的性能都不错,但是不适合插入数据,比较适合静态存储引擎,存储不会改变的数据

  • 二叉搜索树

是具有以下性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

二叉搜索树的搜索效率高,但是其树高影响对磁盘数据块的访问,一个树高 20 的二叉搜索树,一次查询可能需要访问 20 个数据块,就会出现 20 次的磁盘随机读

  • N 叉搜索树

N 取决于数据库的大小
以 InnoDB 的一个整数字段索引为例,这个 N 差不多是 1200。这棵树高是 4 的时候,就可以存 1200 的 3 次方个值,这已经 17 亿了。考虑到树根的数据块总是在内存中的,一个 10 亿行的表上一个整数字段的索引,查找一个值最多只需要访问 3 次磁盘。其实,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。N 叉树由于在读写上的性能优点,以及适配磁盘的访问模式,已经被广泛应用在数据库引擎中了。

InnoDB 索引的数据结构**

InnoDB 中,表是根据主键顺序以索引的形式存放的,这种存储方式称为索引组织表,而 InnoDB 使用 B+Tree 数据结构,因此所有数据都是存储在 B+Tree 中的

每一个索引在 InnoDB 中都对应一个 B+Tree 树

根据叶子节点的内容,索引类型分为主键索引和非主键索引。主键索引的叶子节点存储整行数据,在InnoDB 中也被称为聚簇索引;非主键索引的叶子节点存储的是主键的值,在 InnoDB 中也被称为二级索引

基于主键索引和普通索引查询的区别?

  • 主键索引查询只会搜索主键这一棵树
  • 普通索引查询会先搜索普通索引的树,得到主键之后再去搜索主键的树(回表)

索引维护

B+Tree 为了维护索引的有序性,会出现页分裂和页合并,自增主键的插入模式会减少这两种操作的出现,提高性能并提高数据页的利用效率

主键的长度越小,普通索引的叶子节点越小,占用的空间也就越小

@git-zjx git-zjx added this to MySQL实战45讲 in MySQL Jul 18, 2019
@git-zjx
Copy link
Owner Author

@git-zjx git-zjx commented Feb 25, 2020

如果没有主键的表,有一个普通索引,怎么回表?

没有主键的表,InnoDB会给默认创建一个Rowid做主键

@git-zjx
Copy link
Owner Author

@git-zjx git-zjx commented Feb 25, 2020

一个InnoDB引擎的表,数据量非常大,根据二级索引搜索会比主键搜索快?

只有使用覆盖索引时会

@git-zjx
Copy link
Owner Author

@git-zjx git-zjx commented Feb 25, 2020

非聚集索引上为什么叶子节点不是数据行的地址,而是主键 id?

这个叫作“堆组织表”,MyISAM 就是这样的,各有利弊。在修改了数据的位置的情况,InnoDB 这种模式会更方便些

@git-zjx
Copy link
Owner Author

@git-zjx git-zjx commented Feb 25, 2020

如果磁盘中的主键索引已经存储了这个表的全部数据的话,那常说的没走索引是遍历整个B+树还是其他地方还有整个表的数据呢?

就是遍历这个主键索引的意思

@git-zjx
Copy link
Owner Author

@git-zjx git-zjx commented Feb 25, 2020

InnoDB B+树主键索引的叶子节点存的是什么?

B+树的叶子节点是page (页),一个页里面可以存多个行

@git-zjx
Copy link
Owner Author

@git-zjx git-zjx commented Feb 25, 2020

非叶子节点存储大约 1200个是怎么算出来的?

整型 4 个字节,加上辅助数据差不多每个key占13字节,16k/13

@git-zjx
Copy link
Owner Author

@git-zjx git-zjx commented Feb 25, 2020

为什么树高20就是20个数据块?

每个叶子结点就是一个块,每个块包含两个数据,块之间通过链式方式链接。树高20的话,就要遍历20个块

@git-zjx git-zjx self-assigned this Mar 2, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
MySQL
MySQL实战45讲
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
1 participant