问题

• 数据库查询 分为等值查找和范围查找
• select * from t where a = 1;

• select * from t where a>20 and a<100;

  尝试数据结构

• 散列表 查询O(1) 但不支持范围查找

• 二叉查找树 O(logn) 中序遍历可以得到有序的数据 但是范围查找太慢

• 跳表 O(logn) 支持范围查找

  改造二叉查找树

• 把非叶子节点全部作为索引 叶子节点用链表串起来作为数据关键字

优化

• 叶子节点有n个，索引也占n个 一个节点10B 就会占用1GB的空间

• 用时间换空间 把索引存储在硬盘上 但是io速度慢

  降低io次数 降低树的高度

• 改造成m叉树，增加所有节点的子树 1亿个节点就三层树

• m越大树的高度越小 但是一个节点的大小 等于操作系统一页的大小 m是固定的

  索引带来的问题

• 索引可能导致更新变慢 因为索引也需要更新

• 节点的子树指针如果大于m 节点会分裂成两个节点 然后从下到上依次分裂

• 删除节点也会变慢 因为一个节点中子节点个数少了 查询效率变低了 设置阈值为m/2 低于这个值可以将两个节点合并

B+树的特点总结

• 每个节点中子节点的个数不能超过 m，也不能小于 m/2；
  
• 根节点的子节点个数可以不超过 m/2，这是一个例外；
  
• m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表；
  
• 通过链表将叶子节点串联在一起，这样可以方便按区间查找；
  
• 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。
  
• B树叶子结点不串链表 并且非叶子节点存储数据