索引是一种加快查询速度的数据结构,常用索引结构有hash、b-tree和b+tree。本节通过分析三者的数据结构来说明为啥mysql选择用b+tree数据结构。
hash是基于哈希表完成索引存储,哈希表特性是数据存放是散列的。
优点:
等值查询快,通过hash值直接定位到具体的数据。
缺点:
b-tree特点:
b+tree 是在b-tree的基础之上做的一种优化,变化如下:
mysql官网文档中写到innodb索引用的是 b-tree,但是底层用的是b+tree。mysql存储数据是以页为单位,默认一个页可以存放16k数据。假设b-tree和b+tree都是3层深度,表中每个记录为1k(假设的,一般不会这么大,别较真),那么三层深度的b-tree存储 16 x 16 x 16 = 4096(比这个数还要少,因为每个页中还要存放指针和其它的数据)。b+tree第一、二层存放的是key,假设是long类型的主键,那么第一、二层每页存放数据约为 16 x 1024 / 8 = 2048,三层深度可以存放 2048 x 2048 x 16 = 6700w。mysql查询过程是按页加载数据的,每加载一页就是一次io操作,b+tree进行三次io可以查询6700w数据量。从这里也可以知道mysql一般设置三层深度就足够了。
如对本文有疑问, 点击进行留言回复!!
网友评论