THIS REPORT IS ONE OF A SERIES DESCRIBING THE DEVELOPMENT OF THE MULTICS MULTILEVEL DATA BASE SYSTEM. THE SYSTEM IS BASED ON A SECURITY KERNEL WHICH (1) MUST PROVIDE COMPLETE MEDIATION (THAT IS, SECURITY CONTROLS MUST BE INVOKED AT EVERY ATTEMPTED ACCESS TO THE OBJECTS OF THE SYSTEM) AND (2) MUST BE ISOLATED FROM THE NONSECURITY PORTIONS OF THE SYSTEM. IT MUST ALSO BE SIMPLE ENOUGH TO BE AMENABLE TO CERTIFICATION. SEVERAL HARDWARE DEVICES ARE AVAILABLE TO MEET THESE REQUIREMENTS. THE MAJOR PROBLEMS INVOLVE THE SOFTWARE DESIGN. SEVERAL POSSIBLE SOLUTIONS ARE DISCUSSED. THE DATA ITEM COULD BE USED AS THE BASIC SECURITY OBJECT, BUT THIS WOULD FORCE STORAGE OF ONE DATA ITEM PER SEGMENT WHICH IS INTOLERABLY EXPENSIVE. IF HOMOGENEOUSLY CLASSIFIED DATA ITEMS ARE STORED IN A SEGMENT, COSTS WOULD BE REDUCED. HOWEVER, DATA FIELD ORGANIZATION GIVES INEFFICIENT ACCESS. EXPERIENCE WITH THE TIME-SHARED DATA MANAGEMENT SYSTEM INDICATES THAT THIS APPROACH IS PRACTICABLE FOR MILITARY APPLICATIONS ONLY WHEN ADAPTED TO MORE CONVENTIONAL DATA ORGANIZATION. HOWEVER, IF THE FIELDS ARE ORGANIZED AS BINARY SEARCH TREES, SEARCH, SEQUENTIAL PROCESSING, INSERTION AND DELETION CAN BE ACCOMPLISHED TO MILITARY SECURITY LEVELS AT A MORE REASONABLE COST. THE EFFECTS OF MILITARY SECURITY ON BOTH INDEXING AND THE DATA STRUCTURE ARE REVIEWED. SINCE BOTH THE SOFTWARE AND THE PERSONNEL OPERATING IT MUST UNDERGO APPROPRIATE SECURITY CLASSIFICATION, A MILITARY SYSTEM WILL COST MORE THAN A COMPARABLE CIVILIAN SYSTEM. (GLR)