读写模型整理笔记

读模型

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