索引数据结构详解
Hash
- 应用哈希算法；
- 数组+链表；
-
哈希碰撞问题；
长处
-
从算法工夫复杂度剖析来看，哈希算法工夫复杂度为 O（1），检索速度十分快。比方查找 id=1 的数据，哈希索引只须要计算一次就能够获取到对应的数据，检索速度十分快。
毛病
- 如果应用哈希算法实现的索引，SQL的范畴查找怎么做呢？一个简略的思路就是一次把所有数据找进去加载到内存，而后再在内存里筛选筛选指标范畴内的数据。所以，应用哈希算法实现的索引尽管能够做到疾速检索数据，然而没方法做数据高效范畴查找，因而哈希索引是不适宜作为 Mysql 的底层索引的数据结构。
二叉树
- 如果insert的数据从小到大排序，该极其状况下会进化为线性链表，二分查找也会进化为遍历查找，工夫简单进化为 O（N），检索性能急剧下降。
红黑树&&均衡二叉树
- 红黑树：存在右倾趋势，树的高度只是没有线性链表那么夸大；
- 均衡二叉树：AVL 树是个相对均衡的二叉树，因而它在调整二叉树的状态上耗费的性能会更多。每个树节点只存储了一个数据，每次查问都要进行屡次磁盘IO。
- 能够依据这个思路，咱们能够在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。
B树
- 优良检索速度，工夫复杂度：B 树的查找性能等于 O（h*logn），其中 h 为树高，n 为每个节点关键词的个数；
- 每个节点存储多个数据，尽可能少的磁盘 IO，放慢了检索速度；
- 能够反对范畴查找。
B+树
- B树和B+树的区别：
- B树节点存储的是数据，B+树节点存储的是索引，只有叶子结点存在数据。单个节点也能够存储大量索引，使得树的高度升高，较少磁盘IO。（//TODO 回表操作）
- 且叶子结点通过链表连接起来，链表是有序的，在数据的范畴查找场景中更高效。
B+树如何实现索引疾速查找(//TODO)
索引的分类
汇集索引
- 索引项的排序形式和表中数据记录排序形式统一的索引；
非汇集索引
- 索引项程序与物理存储程序不同；
聚簇索引
- InnoDB存储引擎；
- 数据和索引都存储在同一个文件里。比非聚簇索引快，因为聚簇索引多一次磁盘IO。
非聚簇索引
- Myisam存储引擎；
- 一种数据存储形式；表数据和索引是分成两局部存储的，主键索引和二级索引存储上没有任何区别。应用的是B+树作为索引的存储构造，所有的节点都是索引，叶子节点存储的是索引+索引对应的记录的数据。
InnoDB和Myisam的区别
- InnoDB 节约磁盘空间；如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就变得十分微小。
- Myisam 间接找到物理地址后就能够间接定位到数据记录，然而 InnoDB 查问到叶子节点后，还须要再查问一次主键索引树，才能够定位到具体数据。
为什么举荐应用自增主键做索引
- 如果主键为自增 id 的话，MySQL 在写满一个数据页的时候，间接申请另一个新数据页接着写就能够了。
- 如果主键是非自增 id，为了确保索引有序，MySQL 就须要将每次插入的数据都放到适合的地位上。
-
不便范畴查找//TODO（因为索引是有序）
联结索引的底层数据结构
Mysql最左前缀优化准则
- 最左前缀匹配准则和联结索引的索引构建形式及存储构造是有关系的。
- 首先咱们创立的index_bcd(b,c,d)索引，相当于创立了(b)、（b、c）（b、c、d）三个索引，看完上面你就晓得为什么相当于创立了三个索引。
-
联结索引是首先应用多列索引的第一列构建的索引树，用下面idx_t1_bcd(b,c,d)的例子就是优先应用b列构建，当b列值相等时再以c列排序，若c列的值也相等则以d列排序。
select * from T1 where b = 12 and c = 14 and d = 3;-- 全值索引匹配 三列都用到。 select * from T1 where b = 12 and c = 14 and e = 'xml';-- 利用到两列索引。 select * from T1 where b = 12 and e = 'xml';-- 利用到一列索引。 select * from T1 where b = 12 and c >= 14 and e = 'xml';-- 利用到bc两列列索引及索引条件下推优化。 select * from T1 where b = 12 and d = 3;-- 利用到一列索引 因为不能跨列应用索引 没有c列 连不上。 select * from T1 where c = 14 and d = 3;-- 无奈利用索引，违反最左匹配准则。
发表回复