search

AdrianHu99 / NOTES

0 stars 0 forks source link

Mysql的常见面试题 + 索引原理分析 #38

Closed AdrianHu99 closed 5 years ago

AdrianHu99 commented 5 years ago

https://mp.weixin.qq.com/s/ZtuUg79OFLh20-HWs2Qs4A

AdrianHu99 commented 5 years ago

哈希表的特点就是可以快速的精确查询，但是不支持范围查询。

AdrianHu99 commented 5 years ago

由于完全平衡二叉树是有序的，所以也是支持范围查找的。

AdrianHu99 commented 5 years ago

B树的表示要比完全平衡二叉树要“矮”，原因在于B树中的一个节点可以存储多个元素。

AdrianHu99 commented 5 years ago

B+树的表示要比B树要“胖”，原因在于B+树中的非叶子节点会冗余一份在叶子节点中，并且叶子节点之间用指针相连。

AdrianHu99 commented 5 years ago

完全平衡二叉树，当我们需要查询“张飞”时，需要以下步骤

从磁盘中取出“曹操”到内存，CPU从内存取出数据进行笔记，“张飞”<“曹操”，取左子树（产生了一次磁盘IO）

从磁盘中取出“周瑜”到内存，CPU从内存取出数据进行笔记，“张飞”>“周瑜”，取右子树（产生了一次磁盘IO）

从磁盘中取出“孙权”到内存，CPU从内存取出数据进行笔记，“张飞”>“孙权”，取右子树（产生了一次磁盘IO）

从磁盘中取出“黄忠”到内存，CPU从内存取出数据进行笔记，“张飞”=“张飞”，找到结果（产生了一次磁盘IO）

同理，回头看一下B树，我们发现只发送三次磁盘IO就可以找到“张飞”了，这就是B树的优点：一个节点可以存储多个元素，相对于完全平衡二叉树所以整棵树的高度就降低了，磁盘IO效率提高了。

而B+树是B树的升级版，只是把非叶子节点冗余一下，这么做的好处是为了提高范围查找的效率。

AdrianHu99 commented 5 years ago

到这里可以总结出来，Mysql选用B+树这种数据结构作为索引，可以提高查询索引时的磁盘IO效率，并且可以提高范围查询的效率，并且B+树里的元素也是有序的。

AdrianHu99 commented 5 years ago

为什么一个节点为1页（16k）就够了？ 对着上面Mysql中Innodb中对B+树的实际应用（主要看主键索引），可以发现B+树中的一个节点存储的内容是：

非叶子节点：主键+指针

叶子节点：数据

那么，假设我们一行数据大小为1K，那么一页就能存16条数据，也就是一个叶子节点能存16条数据；再看非叶子节点，假设主键ID为bigint类型，那么长度为8B，指针大小在Innodb源码中为6B，一共就是14B，那么一页里就可以存储16K/14=1170个(主键+指针)，那么一颗高度为2的B+树能存储的数据为：117016=18720条，一颗高度为3的B+树能存储的数据为：11701170*16=21902400（千万级条）。所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。所以也就回答了我们的问题，1页=16k这么设置是比较合适的，是适用大多数的企业的，当然这个值是可以修改的，所以也能根据业务的时间情况进行调整。