database structures

src: La base de données : une structure de données sophistiquée et spéciale

Abstract

• structure de données avec la morphologie du support du stockage
• ex: tableau dans un disque dur HDD pas optimal, ça risque de créer des fragmentations, etc…
• ex cas réels
• sqlite, MySQL and PostgreSQL use b-tree indexes
• oracle uses b-tree and bitmap indexes
• couchebase uses magma indexes
• B-Tree: Balanced Tree
• performance: logarithmic time complexity
• toujours équilibré et trié
• clustered index
  • contient les indexes et les données
• pas adapté pour des structures de données distribuées
• efficaces pour les opérations de lecture
• moins efficaces pour les opérations d’écriture
• LSM: Log-Structured Merge Tree
• time complexity
  • insert: O(1)
  • find-min / delete-min: O(n)