mysql索引

mysql索引类型hash和btree，btree的内容基本都还给大学老师了，重新学习下。

btree是一种m阶树，这棵树有以下特征

1、每个节点最多有m个孩子节点

2、除了根节点和叶子节点，其他节点至少要有ceil(m/2)个孩子节点

3、如果根节点不是叶子节点，至少要有2个孩子节点

4、所有叶子节点都在同一层

5、每个节点保存了键值、数据、指针，假设为（k1,k2,....kn,p1,p2....pn），键值为记录的主键值，数据为除主键以外的其他内容，指针指向孩子节点的存储块地址

6、n的取值： ceil(m/2)+1 <= n <= m-1

7、键值按大小排序，p（i）数据块的键值都小于(ki),但是大于k(i-1)

b树查找时每向下一层，就需要读取一个存储块，深度越大io消耗越多。

b+树跟b树的区别是节点里不包含数据，数据都在叶子节点，非叶子节点只保存键值和指针。优点是每个非叶子节点能够保存更多的键值，减少树的深度