索引是帮助 MySQL 高效获取数据的排好序的数据结构

索引数据结构

二叉树 Binary Search Tree

• 弊端: 连续id二叉树会变成和链表差不多的结构. 效率不高

红黑树 Red/Black Tree

平衡二叉树

• 弊端: 树的高度太高

Hash 表

• 对索引的 key 进行一次 hash 计算就可以定位出数据存储的位置
  • 很多时候 Hash 索引要比 B+ 树索引更高效
  • 仅能满足 “ =” ，“ IN” ，不支持范围查询
  • hash 冲突问题

B Tree

• 叶节点具有相同的深度，叶节点的指针为空
• 所有索引元素不重复
• 节点中的数据索引从左到右递增排列

B+ Tree ( B树变种)

• 非叶子节点不存储 data ，只存储索引 ( 冗余 ) ，可以放更多的索引