MongoDB 設計中的演算法概念

1. 滑動視窗概念

在 MongoDB 中的應用

// Sliding Window for Time-Series Data
db.userActivity.aggregate([
  // Sliding window for last 30 days of user engagement
  {
    $match: {
      timestamp: {
        $gte: new Date(Date.now() - 30 * 24 * 60 * 60 * 1000)
      }
    }
  },
  {
    $group: {
      _id: {
        // Group by day
        day: { $dateToString: { 
          format: "%Y-%m-%d", 
          date: "$timestamp" 
        }}
      },
      dailyActiveUsers: { $addToSet: "$userId" },
      totalEvents: { $sum: 1 }
    }
  },
  // Sliding window aggregation to track trends
  {
    $setWindowFields: {
      sortBy: { "_id.day": 1 },
      output: {
        movingAverageUsers: { 
          $avg: "$dailyActiveUsers.length", 
          window: {
            range: [-7, 0],
            unit: "day"
          }
        }
      }
    }
  }
])

主要優點

• 追蹤滾動指標
• 分析基於時間的趨勢
• 高效率的記憶體使用

2. 兩指針技術

架構設計範例

// Optimized Social Graph Schema
{
  _id: ObjectId("user1"),
  followers: [
    { 
      userId: ObjectId("user2"),
      followedAt: ISODate(),
      interaction: {
        // Two-pointer like tracking
        mutualFollows: Boolean,
        lastInteractionScore: Number
      }
    }
  ],
  following: [
    { 
      userId: ObjectId("user3"),
      followedAt: ISODate()
    }
  ]
}

// Efficient Friend Recommendation
function findPotentialConnections(userId) {
  return db.users.aggregate([
    { $match: { _id: userId } },
    // Expand followers and following
    { $project: {
        potentialConnections: {
          $setIntersection: [
            "$followers.userId", 
            "$following.userId"
          ]
        }
      }
    }
  ]);
}

優化技術

• 降低運算複雜度
• 高效率的關係追蹤
• 最小化完整集合掃描

3.動態規劃（DP）方法

緩存和記憶

// DP-Inspired Caching Strategy
{
  _id: "user_analytics_cache",
  userId: ObjectId("user1"),
  // Memoized computation results
  cachedMetrics: {
    last30DaysEngagement: {
      computedAt: ISODate(),
      totalViews: 1000,
      avgSessionDuration: 5.5
    },
    yearlyTrends: {
      // Cached computation results
      computedAt: ISODate(),
      metrics: { /* pre-computed data */ }
    }
  },
  // Invalidation timestamp
  lastUpdated: ISODate()
}

// DP-like Incremental Computation
function updateUserAnalytics(userId) {
  // Check if cached result is valid
  const cachedResult = db.analyticsCache.findOne({ userId });

  if (shouldRecompute(cachedResult)) {
    const newMetrics = computeComplexMetrics(userId);

    // Atomic update with incremental computation
    db.analyticsCache.updateOne(
      { userId },
      { 
        $set: {
          cachedMetrics: newMetrics,
          lastUpdated: new Date()
        }
      },
      { upsert: true }
    );
  }
}

4. 索引中的貪婪方法

索引策略

// Greedy Index Selection
db.products.createIndex(
  { 
    category: 1, 
    price: -1, 
    soldCount: -1 
  },
  {
    // Greedy optimization
    partialFilterExpression: {
      inStock: true,
      price: { $gt: 100 }
    }
  }
)

// Query Optimization Example
function greedyQueryOptimization(filters) {
  // Dynamically select best index
  const indexes = db.products.getIndexes();

  const bestIndex = indexes.reduce((best, current) => {
    // Greedy selection of most selective index
    const selectivityScore = computeIndexSelectivity(current, filters);
    return selectivityScore > best.selectivityScore 
      ? { index: current, selectivityScore }
      : best;
  }, { selectivityScore: -1 });

  return bestIndex.index;
}

5. 堆/優先權佇列概念

分散式排名系統

// Priority Queue-like Document Structure
{
  _id: "global_leaderboard",
  topUsers: [
    // Maintained like a min-heap
    { 
      userId: ObjectId("user1"),
      score: 1000,
      lastUpdated: ISODate()
    },
    // Continuously maintained top K users
  ],
  updateStrategy: {
    maxSize: 100,
    evictionPolicy: "lowest_score"
  }
}

// Efficient Leaderboard Management
function updateLeaderboard(userId, newScore) {
  db.leaderboards.findOneAndUpdate(
    { _id: "global_leaderboard" },
    {
      $push: {
        topUsers: {
          $each: [{ userId, score: newScore }],
          $sort: { score: -1 },
          $slice: 100  // Maintain top 100
        }
      }
    }
  );
}

6.圖形演算法靈感

社群網路架構

// Graph-like User Connections
{
  _id: ObjectId("user1"),
  connections: [
    {
      userId: ObjectId("user2"),
      type: "friend",
      strength: 0.85,
      // Inspired by PageRank-like scoring
      connectionScore: {
        mutualFriends: 10,
        interactions: 25
      }
    }
  ]
}

// Connection Recommendation
function recommendConnections(userId) {
  return db.users.aggregate([
    { $match: { _id: userId } },
    // Graph traversal-like recommendation
    { $graphLookup: {
        from: "users",
        startWith: "$connections.userId",
        connectFromField: "connections.userId",
        connectToField: "_id",
        as: "potentialConnections",
        maxDepth: 2,
        restrictSearchWithMatch: {
          // Avoid already connected users
          _id: { $nin: existingConnections }
        }
      }
    }
  ]);
}

可擴展性考慮因素

主要原則

1. 演算法效率

   • 最小化集合掃描
   • 策略性地使用索引
   • 實現高效聚合

2. 分散式計算

   • 利用分片
   • 實作智慧分割區
   • 使用聚合管進行分散式計算

3. 緩存與記憶

   • 快取複雜的計算
   • 使用基於時間的失效
   • 實施增量更新

關鍵技能

• 了解資料存取模式
• 了解索引策略
• 認識查詢複雜度
• 考慮水平縮放

以上是MongoDB 設計中的演算法概念的詳細內容。更多資訊請關注PHP中文網其他相關文章！