初识索引

• 索引是应用程序设计和开发的一个重要方面。若索引太多，应用程序的性能可能会受到影响。而索引太少，对查询性能又会产生影响，要找到一个平衡点，这对应用程序的性能至关重要。
• 优点：可以快速检索，减少I/O次数，加快检索速度；根据索引分组和排序，可以加快分组和排序。
• 缺点：索引本身也是表，因此会占用存储空间，一般来说，索引表占用的空间的数据表的1.5倍；索引表的维护和创建需要时间成本，这个成本随着数据量增大而增大；构建索引会降低数据表的修改操作（删除，添加，修改）的效率，因为在修改数据表的同时还需要修改索引表。
• 什么时候要使用索引？1.主键自动建立唯一索引；2.经常作为查询条件在WHERE或者ORDER BY 语句中出现的列要建立索引；3.作为排序的列要建立索引；4.查询中与其他表关联的字段，外键关系建立索引；5.高并发条件下倾向组合索引。
• 什么时候不要使用索引？1.经常增删改的列不要建立索引；2.有大量重复的列不建立索引；3.表记录太少不要建立索引。

索引的原理

数据结构：B+树

B+数的特征

B+树是一个n叉树，每个节点通常有多个孩子，一颗B+树包含根节点、内部节点和叶子节点。B+树通常用于数据库和操作系统的文件系统中。 B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。 B+树元素自底向上插入。
一个m阶的B树具有如下几个特征：

• 根结点至少有两个子女。
• 每个中间节点都至少包含ceil(m / 2)个孩子，最多有m个孩子。
• 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。
• 所有的叶子结点都位于同一层。
• 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
  

  B+树和B树的区别

• 有k个子结点的结点必然有k个关键码；
• 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
• 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

参考资料

https://www.cnblogs.com/Eva-J/articles/10126413.html
https://www.jianshu.com/p/71700a464e97