什么是索引，索引结构和数据库原理？( 二 )

如上图所示，一棵B树包含有键值、存储子节点的指针信息、及除主键外的数据。相对于普通的树BTree将横向节点的容量变大，从而存储更多的索引。
1.4 B+Tree在B-Tree的基础上大牛们又研究出了许多变种，其中最常见的是B+Tree，MySQL就普遍使用B+Tree实现其索引结构。

文章插图
与B-Tree相比，B+Tree做了以下一些改进：1、非叶子节点，只存储键值信息，这样极大增加了存放索引的数据量。2、所有叶子节点之间都有一个链指针。对于区间查询时，不需要再从根节点开始，可直接定位到数据。3、数据记录都存放在叶子节点中。根据二叉树的特点，这个是顺序访问指针，提升了区间访问的性能。通过这样的设计，一张千万级的表最多只需要3次磁盘交互就可以找出数据。
二、Mysql部分原理说明这一部分我们选举几个日常面试过程中或者使用过程中比较常见的问题通过问答的形式来进行讲解。
2.1、数据库引擎MyISAM和InnoDB有什么区别2.2 表和数据等在Mysql中是如何存储的我们新建一个数据库mds_demo，里面有两张表：order_info,user

文章插图
我们找到mysql存放数据的data目录，存在一个mds_demo的文件夹，同时我们也找到了order_info和user的文件。

文章插图
为什么两张表产生了不同的文件呢？原因很简单，因为创建这两张表时使用了不同的引擎

文章插图

文章插图
2.3 为什么InnoDB必须要有主键，并且推荐使用整型的自增主键？通过上面的讲解这个问题其实已经很清楚了，为了满足MySQL的索引数据结构B+树的特性，必须要有索引作为主键，可以有效提高查询效率。有的童鞋可能会说我创建表的时候可以没有主键啊，这个其实和Oracle的rownum一样，如果不指定主键，InnoDB会从插入的数据中找出不重复的一列作为主键索引，如果没找到不重复的一列，InnoDB会在后台增加一列rowId做为主键索引。所以不如我们自己创建一个主键。
将索引的数据类型是设置为整型，一来占有的磁盘空间或内存空间更少，另一方面整型相对于字符串比较更快速，而字符串需要先转换为ASCII码然后再一个个进行比较的。
参见B+树的图它本质上是多路多叉树，如果主键索引不是自增的，那么后续插入的索引就会引起B+树的其他节点的分裂和重新平衡，影响数据插入的效率，如果是自增主键，只用在尾节点做增加就可以。
最后特别强调一点：不管当前是否有性能要求或者数据量多大，千万不要使用UUID作为索引。
2.4 为什么Mysql存储引擎中默认每个页的大小为16KB？假设我们一行数据大小为1K，那么一页就能存16条数据，包含指针+数据+索引。假设一行数据大小为1K，那么一页（1个叶子节点）就能存16条数据；对于非叶子节点，假设ID为bigint类型那么长度为8B，指针大小在Innodb源码中为6B，一共就是14B，那么一页里就可以存储16K/14=1170个(主键+指针)，这样一颗高度为3的B+树能存储的数据为：1170117016=2千万级别。所以我们前面1000万的数据只有0.02s 。
2.5 HASH算法的使用场景

文章插图
Hash算法是一种散列算法，就是计算出某个字段的hash，然后存放在对应的地址中，查找数据时只需要1次定位而不像BTree那样从根节点找到叶子节点经过多次IO操作，所以查询效率非常地高。但同样也有很多的弊端，讲一下最重要的两条。1、很明显hash只支持=、IN等查询，而不支持范围查询2、 Hash 索引在任何时候都不能避免表扫描。