Mysql(1)数据结构

1 mysql使用的数据结构（B+树+Hash）

1.1 B+树

几个特点 ：
1.非叶子节点不存储data，只存储索引，因此 可以存储更多的索引
2.叶子节点包含所有的索引+数据
3.叶子节点使用指针链接，提高区间访问性能
4.叶子节点之间存在 双向指针

举例：查询30，只需要三次磁盘io

1.2 Hash

hash索引无法 支持范围查找

2 相似数据结构（二叉树，红黑树，b-树）

2.1 二叉树

定义：只有两个分叉的树。为度不超过2的树

查询效率：查23，三次磁盘io
如果使用二叉树作为mysql存储数据结构，定义一个自增主键的数据库表

根据二叉树增加原则，造成数据存储类似于链表，无法起到提升效率的作用

2.2 红黑树

自平衡二叉查树
五个性质特点：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
三操作保证红黑树的平衡
左旋、右旋和变色

为什么不用红黑树：1，红黑树是二叉树，数据量大时树的深度会很深，查询磁盘io次数很多

2.3 B-树

B-树是多路搜索树，与b+树不同在于B-树的每个节点都会存储 数据信息

3 存储引擎数据存储结构（）innodb，myisam

3.1 存储引擎是针对数据库表来说的

3.2 两种存储引擎的数据存储位置与不同

3.3 见建表使用整型自增主键

原因：整型占用空间小，索引比较速度快