数据库索引事务与主从同步

索引

• B+树

  优点：

  • 磁盘读取快
  • 支持区间提取
  • 支持左前缀匹配
  • 查询复杂度log(n)，由于磁盘支持顺序读非常好，因此查询可以很快

  缺点：

  • 大数据不占优
  • 写吞吐受限，因为有大量的随机IO，调整树结构也会带来大量的IO

• hash

  优点：

  • kv O(1)访问

  缺点：

  • 不支持区间提取
  • 不能比较大小

• LSM

  解决b树写慢的问题

  组成：

  • Memstore，用于保存最新写入的数据，是一个内存的有序集，可以用跳跃表实现，update，delete，insert都不会改变StoreFile的数据，会以追加的方式写入Memstore
  • HLog，每次写入都是先写log，使得可以重建Memstore在遇到故障时
  • StoreFile，当Memstore达到一定大小的时候，数据会存入StoreFile（磁盘），磁盘上会按时间顺序有多个storeFile

  牺牲了读的性能，提高了写的性能

  优化：

  • Boom过滤器
  • compact
  • 内存LRU算法

• 倒排索引（GIN索引）

• GIST索引

  传统的大于，小于，等于无法满足地理数据之类的运算，例如位于左侧，右侧，包含

  GIST使用R-tree的结构对数据（x,y）进行建索引

db-r-tree

事务

类型

• 读未提交

  会带来脏读

• 读已提交

  解决了脏读，会带来不可重复读

• 可重复读

  解决了不可重复读（针对update，查询同一个字段，两次读不一样），带来了幻读（针对insert和delete，在查询一个区间，两次查询的结果不一样）

  MVCC解决方案：

  • 每个事务都有一个单调递增的commitid，如果事务修改了某条记录，会增加记录修改这条记录的commitid
  • 如果某个事务过来查询，它会比较这条记录的commitid是否大于自己，如果大于则去找更小的commitid的版本，并读取

• 串行化

  解决了幻读

  MVCC解决方案：

  • 读写入的commitid小于自己的commitid的记录
  • 读删除的commitid大于自己的commitid或者删除的commitid为空的记录

  insert：写入commitid

  update：写入原记录的删除commitid，但不删除原记录，写入新记录并写入commitid

  delete：写入原纪录删除commitid，但不删除记录

HA

MYSQL

db-binlog

写binlog的时机：

• 如果配置sync_binlog=0，代表mysql不控制binlog刷新，由操作系统控制缓存刷新
• 如果配置为1，代表一个事务刷新一次binlog，故障时，最多丢失一个事务
• 如果配置为n，代表n个事务刷新一次binlog，故障时，会丢失多个事务

同步类型：

• 异步同步

  不关心同步结果

• 全同步复制

  需要全部slave都执行了事务才返回

• 半同步复制

  至少等待一个slave执行了事务，才返回

POSTGRESQL

通过WAL log来同步，如果master故障，slave会落后一个WAL log的数据。

因此引入了流复制的概念。

流以事务为单位，数据源源不断的从master流向slave。这样做可以大大减少因为故障而丢失数据的数量。

• 同步流复制：一个提交必须等待slave写成功才返回
• 级联流复制：备库可以再连备库
• 逻辑复制：只对某些表复制
• 异步流复制

WAL log写入时机：

• 以事务为单位，再commit后刷新到磁盘