【142期】阿里面试：分析为什么B+树更适合作为索引的结构以及索引原理

点击上方“Java面试题精选”，关注公众号

面试刷图，查缺补漏

>>号外：往期面试题，10篇为一个单位归置到本公众号菜单栏->面试题，有需要的欢迎翻阅

阶段汇总集合：一百期面试题汇总

mysql的B+树索引查找使用了二分查找，redis 跳表也使用了二分查找法，kafka查询消息日志也使用了二分查找法，二分查找法时间复杂度O(logn);

在MySQL中，主要有四种类型的索引，分别为：B-Tree索引，Hash索引，Fulltext索引(MyISAM 表)和R-Tree索引，本文讲的是B-Tree索引。

后面的索引原理一定要看，太重要了，阿里两个人都问这个mysql的索引原理

mysql使用了 B+索引：

B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；

一、Mysql索引主要有两种结构：B+Tree索引和Hash索引

(a) Inodb存储引擎默认是 B+Tree索引

(b) MyISAM 存储引擎默认是Fulltext索引；

(c)Memory 存储引擎默认 Hash索引；

Hash索引

mysql中，只有Memory(Memory表只存在内存中，断电会消失，适用于临时表)存储引擎显示支持Hash索引，是Memory表的默认索引类型，尽管Memory表也可以使用B+Tree索引。

Hash索引把数据以hash形式组织起来，因此当查找某一条记录的时候，速度非常快。但是因为hash结构，每个键只对应一个值，而且是散列的方式分布。所以它并不支持范围查找和排序等功能。

B+Tree索引

B+Tree是mysql使用最频繁的一个索引数据结构，是Inodb和Myisam存储引擎模式的索引类型。相对Hash索引，B+Tree在查找单条记录的速度比不上Hash索引，但是因为更适合排序等操作，所以它更受欢迎。毕竟不可能只对数据库进行单条记录的操作。

带顺序访问指针的B+Tree

B+Tree所有索引数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都有指向相邻叶子节点的指针。

这样做是为了提高区间效率，例如查询key为从18到49的所有数据记录，当找到18后，只要顺着节点和指针顺序遍历就可以以此向访问到所有数据节点，极大提高了区间查询效率。

大大减少磁盘I/O读取

数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点需要一次I/O就可以完全载入。

什么是索引

索引（Index）是帮助数据库高效获取数据的数据结构。索引是在基于数据库表创建的，它包含一个表中某些列的值以及记录对应的地址，并且把这些值存储在一个数据结构中。最常见的就是使用哈希表、B+树作为索引。

一般的应用系统，读写比例在10:1左右，而且插入操作和一般的更新操作很少出现性能问题，在生产环境中，我们遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，因此对查询语句的优化显然是重中之重。说起加速查询，就不得不提到索引了。

为什么要使用索引

我们知道，数据库查询是数据库最主要的功能之一。而查询速度当然是越快越好。而当数据量越来越大的时候，查询花费的时间会随之增长。而索引，可以加速数据的查询。因为索引是有序排列的。

举个例子来说，假设我们有一个数据库表Employee，这个表分别有三个字段：name，age，address。假设表中有1000条记录。

假如没有使用索引，当我们查询名为“Jesus”的雇员的时候，即调用：

SELECT * FROM table_name 
WHERE MATCH(column1, column2) AGAINST('word1', 'word2', 'word3')

上面这条命令将把column1和column2字段里有word1、word2和word3的数据记录全部查询出来。

四、索引使用注意事项

1，不要滥用索引

①，索引提高查询速度，却会降低更新表的速度，因为更新表时，mysql不仅要更新数据，保存数据，还要更新索引，保存索引

②，索引会占用磁盘空间

2，索引不会包含含有NULL值的列

复合索引只要有一列含有NULL值,那么这一列对于此符合索引就是无效的，因此我们在设计数据库设计时不要让字段的默认值为NULL。

3，MySQL查询只是用一个索引

如果where字句中使用了索引的话，那么order by中的列是不会使用索引的

4，like

like ‘%aaa%’不会使用索引而like “aaa%”可以使用索引

往期：一百期面试题汇总

五、选择索引的数据类型

Mysql支持很多数据类型，选择合适的数据类型存储数据对性能有很大的影响。

(1)越小的数据类型通常更好：越小的数据类型通常在磁盘、内存和cpu缓存中都需要更少的空间，处理起来更快。

(2)简单的数据类型更好：整形数据比起字符，处理开销更小，因为字符串的比较更复杂。在MySQL中，应用内置的日期和时间数据类型，而不是字符串来存储时间；以及用整形数据存储IP地址。

(3)尽量避免NULL：应该制定列为NOT NULL，除非你想存储NULL。在MySQL中，含有空值的列很难进行查询优化，因为他们使得索引、索引的统计信息以及比较运算更加复杂。

六、MySQL常见索引有：主键索引、唯一索引、普通索引、全文索引、组合索引

1，INDEX（普通索引）：ALTER TABLE 'table_name' ADD INDEX index_name('col')

最基本的索引，没有任何限制

2，UNIQUE（唯一索引）：ALTER TABLE 'table_name' ADD UNIQUE('col')

与“普通索引”类似，不同的就是：索引列的值必须唯一，但允许有空值。

3，PRIMARY KEY（主键索引）：ALTER TABLE 'table_name' ADD PRIMARY KEY('col')

是一种特殊的唯一索引，不允许有空值。

4，FULLTEXT（全文索引）：ALTER TABLE 'table_name' ADD FULLTEXT('col')

仅可用于MyISAM和InoDB，针对较大的数据，生成全文索引很耗时耗空间

组合索引：ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3')

为了更多的提高mysql效率可建立组合索引，遵循“最左前缀”原则。创建复合索引应该将最常用（频率）做限制条件的列放在最左边，一次递减。

组合索引最左字段用in是可以用到索引的。相当于建立了col1,col1col2,col1col2col3三个索引

参考

http://blog.codinglabs.org/articles/theory-of-mysql-index.html
http://blog.csdn.net/v_JULY_v/article/details/6530142
http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html
https://blog.csdn.net/weixin_30531261/article/details/79312676
https://www.cnblogs.com/bypp/p/7755307.html

作者：aspirant
cnblogs.com/aspirant/p/9214485.html

与其在网上拼命找题？ 不如马上关注我们~

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/7196.html