数据库索引的由来
如果没有索引，当你要在一张数据库表里查找name="kangda"的记录时，就要全表扫描每一条记录。反之索引就是为了解决此问题，用于提升数据库的查找速度。
索引的数据结构
常见的索引数据结构有哈希、数两类。
- 哈希，如HashMap，增删改查的平均时间复杂度都是O(1);
- 数，例如平衡二叉搜索树，增删改查的平均时间复杂度都是O(lg(n));
为什么哈希类型的索引比树型的索引更快，索引结构还要设计成树型呢？（InnoDB不支持哈希索引） - 索引设计成树形，和SQL的需求相关。
- 对于单行查询的SQL需求：select * from user where name="kangda";
这样的SQL确实哈希索引更快，因为只查一条记录。 - 对于排序查询的SQL需求：group by 、order by 、< >
哈希型的索引，时间复杂度会退化为O(n)，而树型的“有序”特性，依然能够保持O(log(n)) 的高效率。
数据库索引为什么使用B+树？
答：根据树种类的特性。
- 二叉搜索树
- 当数据量大的时候，树的高度会比较高，数据量大的时候，查询会比较慢；
- 每个节点只存储一个记录，可能导致一次查询有很多次磁盘IO；
- B数
- 不再是二叉搜索，而是m叉搜索，高度能够大大降低；
- 叶子节点，非叶子节点，都存储数据；
- 中序遍历，可以获得所有节点；
- B树被作为实现索引的数据结构被创造出来，是因为它能够完美的利用“局部性原理”。
- 每个节点可以存储j个记录，如果将节点大小设置为页大小，能够充分的利用预读的特性，极大减少磁盘IO；
- 局部性原理
- 内存读写块，磁盘读写慢，而且慢很多；
- 磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据，每次加载更多的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘IO，提高效率；
- 局部性原理：软件设计要尽量遵循“数据读取集中”与“使用到一个数据，大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘IO；
- B+数
- 非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；
- 叶子之间，增加了链表，获取所有节点，不再需要中序遍历；
B+树对比B树的优点： - 范围查找，定位min与max之后，中间叶子节点，就是结果集，不用中序回溯；
- 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储；
- 非叶子节点，不存储实际记录，而只存储记录的KEY的话，那么在相同内存的情况下，B+树能够存储更多索引；
网友评论