Mysql 索引方法 BTree 和 Hash
BTree 和 Hash 在 MySQL 里是什么
在 MySQL 里的 BTree 和 Hash 指的是数据在存储时所使用的数据结构。
主流的关系型数据库都是使用BTree作为表默认的索引数据结构
什么是BTree
BTree 也就是平衡树;
BTree有以下特点:
- 所有非叶子节点只存储键值信息。
- 所有叶子节点之间有一个链指针
- 数据记录都在叶子节点中
通常在 BTree 上有两种头指针，一个指向根节点，一个指向关键字最小的叶子节点，而且所有叶子节点之间通过链指针连接起来形成一个链式环结构。
因此可以对BTree进行两种查询：
- 对于主键范围查找
- 从根节点开始进行查找
参考资料:BTree和B+Tree详解
什么是Hash
哈希表，是根据关键码值(Key Value)而直接进行访问的数据结构。 也就是说他通过把关键码值映射到一个位置来访问记录,以加快查找速度。这个映射函数叫做散列函数,这个映射表也叫做散列表。
那么Hash索引就是采用一定的哈希算法，把键值转换成新的哈希值，检索时不需要类似BTree那样从根节点到叶子节点逐级查找，只需要一次哈希算法即可定位到相应的位置，速度非常快
怎么通过hash去查找呢
理想情况下使用Hash函数将被查找的键转为数组的索引。最后根据数组的索引直接取到数据的内存地址。
参考资料:哈希表、哈希索引详解
BTree和Hash的区别是什么呢
- 如果是等值查询，那么Hash索引有着明显的优势，在键值唯一的情况下，Hash索引只需要一次算法就能找到对应的值，而BTree需要从根节点逐级往叶子节点搜索。
- 如果是范围查询的话，BTree就有明显优势,就算是有序的键值通过Hash后都可能变成不连续的，因此Hash索引在范围查询上毫无优势。
- Hash无法完成排序以及like “xx%”这样的模糊查询(这个其实也是范围查询)
- Hash索引不支持符合索引的最左匹配原则
- 在有大量键值重复的情况，Hash索引的效率也是非常低的
MySQL各表引擎支持哪些索引呢
- MyISAM:BTree
- InnoDB:BTree
- Memory/Heap:Hash,BTree
参考资料:mysql 存储引擎对索引的支持
