1。面试真题能介绍下MySQ索引的原理和数据结构吗？b+树和b树有什么区别？MySQL聚集索引和非聚集索引有什么区别？它们分别是如何存储的？MySQL索引的使用原则是什么？如何使用MySQL复合索引？2.面试官的心理分析数据库是30k以内的工程师必问的问题，问数据库的话一定要问mysql。N年前，java工程师可能会出去面试，知道oracle是加分项，现在熟悉大数据hadoop，hbase等技术也是加分项。3、面试题解析（1）索引的数据结构是什么？其实就是让你说说mysql索引的底层数据结构。想请教各位mysql索引的常用使用原则。如果我不够好，我会用SQL问你。这个SQL一般是怎么建索引的？至于什么是指数？这个问题太基础了。大家都知道mysql的索引就是用一种数据结构来组织某一列的数据，然后如果要根据那一列的数据进行查询，不需要扫描全表，只要它基于该特定列。数据结构找到那一列的值，然后找到对应行的物理地址。那么回答面试官的一个问题，mysql的索引是如何实现的呢？答案是，不是二叉树，也不是乱树，而是b+树。很多人都会这样回答，然后面试官肯定会问，那你能说说b+树吗？不过在说b+树之前，先说说什么是b-tree。从数据结构的角度看，b-tree必须满足以下条件：(1)d为大于1的正整数，称为B-Tree度。(2)h为正整数，称为B-Tree的高度。(3)每个非叶子节点由n-1个键和n个指针组成，其中d<=n<=2d。(4)每个叶节点至少包含一个键和两个指针，至多2d-1个键和2d个指针，叶节点的指针全部为null。(5)所有叶节点的深度相同，等于树高h。(6)键和指针是分开的，节点的两端是指针。(7)节点中的键从左到右非递减排列。(8)所有节点组成一个树形结构。(9)每个指针要么为空，要么指向另一个节点。(10)如果某个指针在节点node的最左边且不为null，则指向该节点的所有key都小于v(key1)，其中v(key1)为第一个key的值节点。(11)如果某个指针在node节点的最右边并且不为null，那么指向该节点的所有key都大于v(keym)，其中v(keym)是最后一个key的值节点。(12)如果节点node上的一个指针的左右相邻键分别为keyi和keyi+1且不为null，则所有指向该节点的键都小于v(keyi+1)且大于v（可依）。我也是从网上找的上面的规则。说实话，很少有java程序员能耐心的看懂或者背下来的。很高兴知道它是一棵树。拿一张网上的图给大家看看：比如我们现在有一个表：(idintnamevarcharageint)我们现在建一个索引id:15,56,77,20,49select*fromtablewhereid=49select*fromtablewhereid=15反正大概就是上面这个样子。查找时，从根节点开始二分查找。知道这是个问题就够了。里面的数学算法题，时间不够讲。面试官没想到你会讲里面的数学算法题，因为我估计他自己可能记不住。居住。好了，b树就说完了，我们直接看下一个，b+树。b+树是b树的变体。什么是变体？也就是说，有的在原理上并不相同，稍有变化。对于同一组数据，b-tree和b+tree的排列看起来是不一样的。在mysql中一般使用b+树来实现索引，所以b+树非常重要。b+树和b树的区别在于每个结点的指针的上限是2d，而不是2d+1。内部节点不存储数据，只存储键；叶节点不存储指针。这个图我就不自己画了，我在网上做个图给大家看看：select*fromtablewhereid=15select*fromtablewhereid>=18andid<=49但是索引的一般的数据库都进行了b+树的优化，加入了顺序访问指针，比如网上的一张图片，这样在查找范围的时候就很方便了，比如查找18到49之间的数据：其实你差不多到这里了，大家要仔细看看上面两张图，现场画出b-tree和b+树，然后说说区别，以及通过b+树查找的原理。那么说点稍微高级一点的，因为我上面说的只是最基本最常见的b-tree和b+树，但是mysql中不同的存储引擎对索引的实现是不同的。(2)myism存储引擎的索引实现我们先来看myisam存储引擎的索引实现。拿上图，我们就地画下myisam存储的索引实现。在myisam存储引擎的索引中，每个叶子节点的数据存储了数据行的物理地址，比如0x07，然后我们可以画出一张数据表，一行一行的，每一行对应一个物理地址。索引文件id=15，数据：0x07，0a89，数据行的物理地址。数据文件放在一个单独的文件中。select*fromtablewhereid=15->0x07物理地址->15，张三，22myisam最大的特点就是数据文件和索引文件是分开的。你有看到它吗？首先在索引文件中搜索，然后在数据文件中定位一行。(3)innodb存储引擎的索引就绪。我们来看看innodb存储引擎的索引实现。和myisam最大的区别在于innodb的数据文件本身就是一个索引文件，就是主键key，而叶子节点的数据就是那一行数据。下面我们就用上面的指标，现场手工画出这个指标，让大家感受一下。innodb存储引擎需要一个主键，会根据主键创建一个默认的索引，称为聚簇索引。innodb的数据文件也是一个索引文件。索引存储结构大致如下：15，数据：0x07，一行完整的数据，（15，张三，22）。22、数据：一行完整的数据，（22、李四、30）。也正是因为这个原因，innodb表需要主键，而myisam表不需要主键。另一种是在innodb存储引擎下，如果为非主键的字段创建索引，那么最后一个叶子节点的值就是主键的值，因为主键的值可以是用于根据聚簇索引中主键的值再次查找数据，即所谓的返回表，例如：select*fromtablewherename='张三'。先去name的索引中找到张三对应的叶子节点。叶子节点的数据就是那一行的主键，id=15，然后根据id=15，根据id=15去数据文件中的簇索引（按照主键索引组织）到定位到id=15的行的完整数据，所以这里有一个道理，在innodb下为什么不用UUID生成的超长字符串作为主键呢？因为这样玩会导致索引数据全部为主键值，最终会导致索引变得过大，浪费大量的磁盘空间。还有一个原因。在一般的innodb表中，推荐统一使用auto_increment自增值作为主键值，因为这样可以保留聚簇索引，直接增加记录。如果使用非单调递增的主键值，可能会导致b+树分裂后的重组浪费时间。(4)指标使用规则一般来说，跳槽时一定要问指标。b+树索引的结构一般就是怎么存储的。一个问题，这条sqlselect*fromtablewherea=1andb=2andc=3应该怎么建索引，你知道吗，怎么建索引才能保证这条sql使用索引来查询呢？各位同学，说到这里你应该知道具体的myisam和innodb索引了，同时也知道什么是聚簇索引，现场手绘应该就可以了。然后说说一些最基本的使用索引的基本规则。其实最基本的东西，作为一个javacoder，你要知道最左前缀匹配原则，这个东西是和联合索引（compositeindex）相关联的，也就是说，你往往不会一一对应每个字段索引，但是联合索引是为几个索引建立的。给你举个例子，如果你想根据店铺、产品、创建时间三个维度查询一个产品表，那么你可以创建一个联合索引：shop_id、product_id、gmt_create一般来说，你有一个表（product):shop_id,product_id,gmt_create，你的SQL语句应该是根据这3个字段来查询的，所以一般不会只建3个索引，一般来说，你会为平时要查询的几个字段建一个联合索引。java系统写的SQL必须遵守最左前缀匹配原则，保证你所有的SQL都能使用这个联合索引，使用该索引查询createindex(shop_id,product_id,gmt_create)(1)所有列都匹配这个即也就是说，在你的一个sql中，where条件中使用了这3个字段，所以可以使用这个联合索引：select*fromproductwhereshop_id=1andproduct_id=1andgmt_create='2018-01-0110：00:00'(2)最左边的前缀匹配这意味着如果你在你的SQL中使用最左边的一个或多个联合索引列表，你也可以使用这个索引。在索引中查找时，只用最左边的列：select*fromproductwhereshop_id=1andproduct_id=1，这个没问题，可以用这个索引。(3)最左边的前缀匹配，但是中间的某个值不匹配。这意味着如果你在你的SQL中使用联合索引的第一列和第三列，那么第一列的值将被用于索引中搜索。搜索完后，再次扫描结果集，根据第三列进行过滤。第三列不使用索引进行搜索。多了一个过滤工作，但是索引还是可以用的，所以没关系，比如：select*fromproductwhereshop_id=1andgmt_create='2018-01-0110:00:00'就是先在里面搜索根据shop_id=1的索引，查找例如100行记录，然后对这100行记录再次扫描，过滤掉gmt_create='2018-01-0110:00:00'的行。我们在线上系统中经常会遇到这种情况，就是根据联合索引的前一两列，根据索引查找，然后跟着一堆复杂的条件，和函数，只是过滤索引而已搜索结果。是的，根据网上的实践，当单表有百万条数据时，性能还不错。简单的SQL只需要几毫秒，复杂的SQL只需要几百毫秒。可接受的。(4)如果没有最左前缀的匹配，就不行，那就搞笑了，索引肯定用不上，千万别犯这个错误。select*fromproductwhereproduct_id=1，这个肯定不行。(5)前缀匹配意思是如果你不是等价的，比如=,>=,<=操作，而是like操作，那么你必须是like'XX%'才可以使用索引，例如：select*fromproductwhereshop_id=1andproduct_id=1andgmt_createlike'2018%'(6)范围列匹配如果你是范围查询，比如>=,<=，操作之间，只能匹配最左边前缀的规则只能进行范围，范围之后的列不需要建立索引。select*fromproductwhereshop_id>=1andproduct_id=1根据联合索引中的shop_id查询。(7)includefunctions如果对某一列使用函数，比如substring，那么该列就不需要索引了。select*fromproductwhereshop_id=1andfunction(product_id)=2上面是根据上面的shop_id在联合索引中查询（5）索引的缺点和使用索引的缺点，比如常见的一是会增加磁盘消耗，因为占用磁盘文件，高并发时频繁插入和修改索引会导致性能损失。我们的建议是尽量少创建索引，比如一个表一个或两个索引，两个或三个索引，十几个或20个索引，在高并发场景下是可以的。Field，status，100行，status有2个值，0和1。你觉得你建索引还有意义吗？几乎就像全表扫描。select*fromtablewherestatus=1相当于扫描100行中的全部50行。你有一个id字段，每个id都是不同的。创建索引。这时候实际的指标效果就很好了。比如为了定位某个id的行，其实索引二分查找可以大大减少需要扫描的数据量，性能非常好。创建索引时，注意一个选择性问题，选择count(discount(col))/count(*)，可以看到选择性，即该列唯一值占总行数的比例，如果太低的话，说明这个字段的值其实是一样的，或者很多行的值都差不多，那么创建索引几乎没有意义。如果搜索一个值，定位到大量的行，就得重新扫描。就是说一个字段的值几乎都是不一样的，此时使用索引的效果是最好的。还有一个特殊的索引叫前缀索引，也就是说一个字段就是一个字符串，很长。如果要建立索引，最好建立这个字符串的前缀，比如前10个字符。用字符串的前几位创建一个前缀索引，只看不同长度前缀的选择性。一般来说，前缀长度越长，选择性值越高。嗯，同学们，指标可以讨论到这个程度，或者掌握到这个程度。其实在普通的互联网系统中，80%的工作都可以完成，因为在互联网系统中，一般都是尽可能的减少SQL。复杂度，把SQL做的很简单就够了，然后用一个很简单的主键索引（聚集索引）+几个联合索引，就可以覆盖一张表所有的SQL查询需求。对于更复杂的业务逻辑，让其用java代码实现是可以的。大家应该明白，95%的SQL都是单表增删改查。如果你有一些逻辑，比如加入，你可以用java代码来完成。SQL越简单，以后迁移库表、读写分离时成本越低，几乎不需要修改SQL。在这里告诉大家，对于互联网公司来说，用MySQL作为最好的在线实时存储，存储数据，简单的检索；不使用MySQL进行计算，不在MySQL中写join、子查询、函数进行计算，高并发场景；计算放在java内存中，通过写java代码完成；可以合理利用mysql的事务支持。
