读写模型整理笔记

读模型

1、主键读

最常见的读模型,说是主键,其实也包括其它索引键,或者联合主键。

常见实现:hash,时间复杂度可以接近 O(1);B 树或变种:时间复杂度接近 O(log(n))。

关于 B 树和变种:

B 树(B-树):本质上是二叉查找树的升级版,变成了平衡的 N 叉查找树,这个 N 的范围根据磁盘一次读取的块大小来调整,这样复杂度 log n 的底数就从 2 变成一个更大的数,减少了树的高度。除此以外,还有一些额外的优化,比如为了插入和删除的性能考虑,通常准备一些预留的空间,只要在当前块或者邻近块中找到空间写入,就避免了开销巨大的所有记录向后偏移的操作。

B 树的阶:

  1. 一棵 m 阶的 B 树最多有 m 棵子树;
  2. 根节点至少有

[……]阅读全文

Java 容器类型复习笔记

data_structures 最近抽空把 java.lang 下面常用的那些容器类型(数据结构)复习了一下,这些东西是基础,平时使用的时候也可以很容易查得到,有些方法大概知道,但是总是弄混,如果可以记住那些重要方法,并且能够熟练使用的话,还是可以让编码过程变得容易很多。另外一个是实现机制,对于常用数据结构的实现机制,应该说是必须要熟知的。

另外,并发容器我之前整理过,放在这篇文章里。

Queue

  1. add 和 offer 的区别在于达到上限时 add 抛出异常,offer 返回 false;
  2. remove 和 poll 的区别在于,队列为空时前者抛出异常,后者返回空;
  3. element 和 peek 都返回队列头部元素,但是前者失败不抛出异常,后者返回

[……]阅读全文

数据挖掘学习笔记:分类、统计学习

ICDM(国际数据挖掘大会)2006 年从 18 种提名的数据挖掘算法中投票选出了十大算法。这 18 中提名数据挖掘算法分属 10 大数据挖掘主题,蓝色部分即为最终选出的十大算法:

  • 分类(Classification)
    • C4.5
    • CART
    • K Nearest Neighbours
    • Naive Bayes
  • 统计学习(Statistical Learning)
    • SVM
    • EM
  • 关联分析(Association Analysis)
    • Apriori
    • FP-Tree
  • 链接挖掘(Link Mining)
    • PageRank
    • HITS
  • 聚类(Clustering)
    • K-Means
    • BIRC

[……]阅读全文

back to top